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;
}
};