leetcode739.每日温度

题目

给定一个整数数组 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 <= 105
30 <= temperatures[i] <= 100

解答

单调栈

解本题的第一种解题思路是直接进行暴力模拟。但是本文的样例中，若数组的长度很长而且元素都是同一个值，会导致超出时间限制，因此我们必须考虑使用其他的数据结构帮助我们进行解题。本体可以使用栈的数据结构帮助我们解题，思路如下：首先初始化答案数组为全0，数组的长度为temperatures数组的长度，栈中的元素是尚未找到下一个更高温度的索引。遍历温度列表时，如果当前温度大于栈顶索引对应的温度，说明栈顶索引对应的温度已经找到了下一个更高温度，可以计算出答案并更新结果数组。通过这种方法，可以在一次遍历中完成计算，时间复杂度为 O(n)，满足时间限制。C++代码实现如下：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int len = temperatures.size();
        vector<int> answers(len, 0); // 储存答案数组
        stack<int> stk; // 单调栈
        for (int i = 0; i < len; i++) {
            while (!stk.empty() && temperatures[stk.top()] < temperatures[i]) { // 当当前温度高于栈顶索引的温度时
                answers[stk.top()] = i - stk.top(); // 更新对应索引的answer
                stk.pop(); // 较低的温度的索引出栈
            }
            stk.push(i); // 较高的温度索引入栈
        }
        return answers; // 返回答案数组
    }
};

当给定输入 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，我们可以逐步执行优化后的代码来帮助您理解它的工作原理：

初始化空栈和答案数组：stk = []，answers = [0, 0, 0, 0, 0, 0, 0, 0]。
遍历温度列表：
- 对于第一个温度 73：
  - 栈为空，将索引 0 压入栈。
- 对于第二个温度 74：
  - 栈顶索引对应的温度是 73，74 > 73，可以计算答案 answers[0] = 1。
  - 弹出栈顶索引 0，将索引 1 压入栈。
- 对于第三个温度 75：
  - 栈顶索引对应的温度是 74，75 > 74，可以计算答案 answers[1] = 1。
  - 弹出栈顶索引 1，将索引 2 压入栈。
- 对于第四个温度 71：
  - 栈顶索引对应的温度是 75，71 < 75，将索引 3 压入栈。
- 对于第五个温度 69：
  - 栈顶索引对应的温度是 71，69 < 71，将索引 4 压入栈。
- 对于第六个温度 72：
  - 栈顶索引对应的温度是 69，72 > 69，可以计算答案 answers[4] = 2。
  - 弹出栈顶索引 4，将索引 5 压入栈。
- 对于第七个温度 76：
  - 栈顶索引对应的温度是 72，76 > 72，可以计算答案 answers[5] = 1。
  - 弹出栈顶索引 5，将索引 6 压入栈。
- 对于最后一个温度 73：
  - 栈顶索引对应的温度是 76，73 < 76，将索引 7 压入栈。
完成遍历后，栈中剩余的索引对应的答案无法计算，因为它们没有找到下一个更高温度。因此，答案数组中仍然为0。

最终的答案数组为 [1, 1, 4, 2, 1, 1, 0, 0]，它表示每个温度需要等待的天数，直到出现更高的温度。