503.下一个更大元素II

发表于： 分类于：
字数： 730 阅读：≈ 2分钟

🧭 503.下一个更大元素II

给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。

数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。

思路

基本思想

相比于 739题 ，增加了一个限制条件，数组变成循环数组，走到最后会回到开始，并且找到第一个比自己大的元素时，存储到不是元素的下标，而是元素的值

所以为了实现循环，当前元素下标变化不再是简单的++i，而是变成(i+1)%nums.size()，这样即使走到了末尾也会回到开头，也就是末尾的下一个元素是开头的元素，可以模拟遍历两次nums，这样就可以变成循环数组

执行流程

  1. 初始化ans数组全为-1，因为一旦元素找不到比自己大的元素，结果就为1
  2. 设置元素遍历两遍，这样就可以走一圈走到自身，并且还不至于一直循环
  3. 返回最终的结果

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> s;
        vector<int> ans(nums.size(),-1);
        s.push(0);
        //这里不用for(int i=1;i<nums.size();(i+1)%nums.size())
        //否则会陷入死循环
        for(int i=1;i<nums.size()*2;++i){
            if(nums[i%nums.size()]<=nums[s.top()]){
                s.push(i%nums.size());
            }else{
                while(!s.empty()&&nums[i%nums.size()]>nums[s.top()]){
                    ans[s.top()]=nums[i%nums.size()];
                    s.pop();
                }
                s.push(i%nums.size());
            }
        }
        return ans;
    }
};

总结

元素至多找一圈就可以找到第一个比自己大的元素，代码中模拟遍历了两遍nums，是为了控制最终代码能够正常结束，如果遍历逻辑为：

1

for(int i=1;i<nums.size();(i+1)%nums.size())

那么代码永远不会停止，因为i永远小于nums.size()，但是正确答案已经存储到了ans当中，所以代码控制遍历的长度，两边以内肯定可以找到最终的结果

整个数组中肯定只有一种元素找不到第一个比自己大的元素，因为他就是全局最大的元素

遍历两遍是为了控制循环可以正常退出，并且遍历两遍一定可以找到最终的结果

一旦出现当前元素大于栈顶元素，那么栈顶元素就找到了第一个更大的元素，因为是