Leetcode 739.每日温度

题目描述：

请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:

1
2

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

示例 2:

1
2

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

示例 3:

1
2

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

提示：

• $1 <= temperatures.length <= 10^5$
• $30 <= temperatures[i] <= 100$

链接：

https://leetcode-cn.com/problems/daily-temperatures

题目分析

  这道题要寻找的是“之后几天”出现了更高的温度，那遍历的顺序应该是从右向左。对于一个更高的温度，它右边所有低于它的温度就失去作用了，这是因为如果 i 低于右边的温度，那 i 也肯定低于当前的温度，而当前温度比右边的温度更“早”出现，所以答案肯定不会是右边的温度。我们只需要维护从右到左逐渐降低的温度，它们才可能是答案，这其实就符合单调栈的特性（可以直接点击 单调栈 标签跳转到同类型的题目）。
  我们从右到左遍历，对于每个温度，我们查询栈顶，如果栈顶温度大于当前温度，那么栈顶就是答案；而如果栈顶温度小于当前温度，则栈顶失去作用，出栈，这样直到栈顶温度大于当前温度，或者是栈空，我们就得到了答案。然后再将当前温度入栈。
  注意这里是要填入“几天后”，也就是与答案下标的距离，那么我们直接将下标入栈而不是温度入栈（温度可以通过下标查询到），这样可以快速获取答案。注意一下等于也是需要出栈的（不算做更高的温度）还有栈空的情况就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        vector<int> result(temperatures.size());
        stack<int> stk;
        for(int i = temperatures.size() - 1; i >= 0; i--){
            while(!stk.empty() && temperatures[i] >= temperatures[stk.top()]){
                stk.pop();
            }
            result[i] = stk.empty() ? 0 : stk.top() - i;
            stk.push(i);
        }
        return result;
    }
};

  时间复杂度：$O(n)$，其中 $n$ 是数组的大小。我们对数组进行了一次遍历。
  空间复杂度：$O(n)$，其中 $n$ 是数组的大小。我们维护了一个单调栈，栈的大小不会超过 $n$。答案数组不计入空间复杂度中。