给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:

输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：

1 <= temperatures.length <= 10(5)

30 <= temperatures[i] <= 100

对于每个位置寻找向右看到的第一个大于自身的值，很容易想到最右边的没有，所以直接填0

可以考虑倒着看，如果自身比后面的元素大，那很明显后面的元素为无效元素

这种左边大的元素能覆盖右边小元素，想到使用单调栈记录下标，每次遇到左边大元素时把栈内小元素弹出即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> dailyTemperatures(vector<int> &temperatures) {
        stack<int> s;
        int n = temperatures.size();
        vector<int> ans(n);
        for (int i = n - 1; i >= 0; i--) {
            while (!s.empty() && temperatures[i] >= temperatures[s.top()]) {
                s.pop();
            }
            if (s.empty()) {
                ans[i] = 0;
            } else
                ans[i] = s.top() - i;

            s.push(i);
        }
        return ans;
    }
};

或者正向遍历，用单调递增栈，每次弹出时再更新前面的元素