Description

给定一个数组\(a\),求出每一个下标的NGE (Next Greater Element)。要求返回一个与\(a\)相同长度的数组\(b\),值为下标之差。

Constraints

要求算法复杂度\(O(n)\)。

Solution

明面上的单调栈问题,个人简单复习。

既然要NGE,那么当前数比\(top\)更大时就是答案,这里只记录下标。

简单输入示例:[1,1,2]

Code

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        auto &temps = temperatures;
        stack<int> stk;
        vector<int> ans(temps.size());
        for(int i = 0; i < temps.size(); i++) {
            while(!stk.empty() && temps[i] > temps[stk.top()]) {
                auto j = stk.top();
                stk.pop();
                ans[j] = i - j;
            }
            stk.emplace(i);
        }
        return ans;
    }
};

LeetCode-739 Daily Temperatures