正文索引 [隐藏]

传送门

思路

最粗暴的方法就是O(n²)，这题也没卡暴力，可以击败5%混过去，但可以用单调栈来优化。

众所周知，单调栈致力于解决“寻找首个大于(小于)当前位置的值”，要明白单调栈的优势，就要搞清楚它的原理。

常规方法慢在挨个枚举，对每个元素都去一个个的找满足条件的值，那自然是慢的。如果说暴力的思路是“用每个值去找答案”，那单调栈的思路可以形象地理解为“让答案自己去找值”。

就本题而言，单调栈中存的是还没有找到答案的下标，他们自底向上严格上升。在遍历中，如果当前栈顶下标对应的值比nums[i]小，那么nums[i]就是当前值答案，将nums[i]计入ans中并弹出当前下标即完成一次操作。

这样做的正确性是显然地，因为有栈的后入先出特性做保证，当前nums[i]一定最有可能是栈顶元素的答案。

更具体地，因为这题是循环数组，所以需要遍历两次，初始化ans数组为全-1就可以避免最后再来为栈内未出栈的元素赋-1的操作。

代码

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        const int n = nums.size();
        stack<int> stk;
        vector<int> ans(n, -1);

        stk.push(0);
        for (int i = 0; i < n; i++) {
            while(!stk.empty() && nums[stk.top()] < nums[i]) {
                ans[stk.top()] = nums[i];
                stk.pop();
            }
            stk.push(i);
        }
        for (int i = 0; i < n; i++) {
            while(!stk.empty() && nums[stk.top()] < nums[i]) {
                ans[stk.top()] = nums[i];
                stk.pop();
            }
            stk.push(i);
        }

        return ans;
    }
};