739. Daily Temperatures

相关问题：496. Next Greater Element I 

问题：

给定按照日期推移的每日温度列表。

求每一天，距离下一个更暖和的日子还需要的天数。

For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].

Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100].

　　

解法：Monotonic stack（单调递增栈）

同相似问题 496. Next Greater Element I 

站在pop者的角度：

可以求出右边第一个>它的数。

我们要做的只是，求出两者之间的距离。

stack中保存index。那么二者之间的距离即是：（假设：当前 index: i）

res[stack.top()] = i-stack.top()

代码参考：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& T) {
        int n=T.size();
        vector<int> res(n, 0);
        stack<int> s;//idx
        for(int i=0; i<T.size(); i++) {
            while(!s.empty() && T[s.top()]<T[i]) {
                res[s.top()]=i-s.top();
                s.pop();
            }
            s.push(i);
        }
        return res;
    }
};