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