leetcode 503.下一个更大元素II 单调栈

题目描述

下一个更大元素II：原题链接

---

思路

利用单调栈的思想

1. 这里要处理的数组是循环数组，但是输出的时候，还是输出原数组对应的答案，所以可以先进行处理，将原数组转化为一个伪循环数组。
   即将数组$[\mathrm{0...}n-1]$转化为数组[0…n-1,0…n-2]
2. 利用单调栈思想进行处理整个数组，从后往前处理，因为题目让求得是每个元素的 下一个更大元素
   单调栈思想参考
3. 将答案翻转，去掉尾部伪循环数组的部分，return结果

---

代码

#include
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        stack<int> s;
        vector<int> res;
        //将原数组后面添上循环的内容，变为线性伪循环数组
        int length=nums.size();
        for(int i=0;i<length-1;i++)
            nums.push_back(nums[i]);
        //从后往前遍历伪循环数组，利用单调栈的思想进行处理    
        for(int i=nums.size()-1;i>=0;i--)
        {
            while(!s.empty()&&s.top()<=nums[i]) 
                s.pop();
            if(s.empty())   //如果不存在，则输出 -1 
                res.push_back(-1);
            else
                res.push_back(s.top());
            s.push(nums[i]);
        }
        //对结果的处理
        reverse(res.begin(),res.end());
        for(int i=0;i<length-1;i++)
            res.pop_back();
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

---