每日温度

给定一个整数数组 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

单调栈：

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector<int> ans(n, 0);
        stack<int> st;

        for (int i = 0; i < n; ++i)
        {
            while (!st.empty() && temperatures[i] > temperatures[st.top()])
            {
                int previous = st.top();
                st.pop();

                ans[previous] = i - previous;
            }

            st.push(i);
        }

        return ans;
    }
};

核心思想

对于每一天，最直接的做法是向后查找第一个更高温度。

如果对每个位置都从后面逐个检查，最坏情况下会重复比较很多次，时间复杂度达到 O(n^2)。

这题需要利用已经扫描过的信息，避免重复查找。

从左到右扫描时，如果今天的温度比栈顶对应的温度高，那么今天就是栈顶那一天一直等待的下一个更高温度。

而且，如果今天的温度还比栈中更早的几天都高，那么这些天也可以一起被解决。

这题最关键的观察是：

栈中保存所有还没有找到更高温度的日期下标，并且这些下标对应的温度从栈底到栈顶单调递减。

因此遇到新温度时：

• 如果新温度不高于栈顶温度，当前日期暂时不能解决任何栈中日期，直接入栈。
• 如果新温度高于栈顶温度，就不断弹出温度更低的日期，并计算它们等待了多少天。

栈中存什么

栈中存的是日期下标，而不是温度值：

stack<int> st;

栈中每个下标都表示：

从这一天开始，还没有找到更高温度

之所以存下标，是因为最终答案需要计算天数差：

answer[previous] = i - previous

虽然栈中保存的是下标，但比较温度时使用：

temperatures[st.top()]

单调性是什么

从栈底到栈顶，对应的温度保持单调递减：

temperatures[st[0]] >= temperatures[st[1]] >= ... >= temperatures[st.top()]

代码使用严格的 > 判断弹栈，因此相同温度可以同时保留在栈中。

例如当前栈对应温度是：

[75, 72, 72, 69]

遇到温度 73 时，会依次解决 69 和一个 72，但不会解决另一个 72，因为 73 对它们都确实更高；相同温度之间的先后顺序由下标区分。

更准确地说，弹栈结束后，栈顶温度一定大于等于当前温度，栈的单调不增性质仍然保持。

为什么遇到更高温度时可以弹栈

假设当前下标是 i，栈顶下标是 j，并且：

temperatures[i] > temperatures[j]

那么对于第 j 天来说，当前第 i 天就是从左到右遇到的第一个更高温度。

因为从 j 到 i 之间的日期都已经被处理过，但它们没有让 j 找到答案。

所以可以确定：

answer[j] = i - j

处理完 j 后把它弹出，继续检查更早的日期。

如果当前温度同样高于更早日期的温度，那么当前日期也可以作为那些日期的答案，因此可以继续弹栈。

为什么相同温度不能直接结算

题目要求的是“更高”温度，而不是“大于等于”当前温度。

所以如果：

temperatures[i] == temperatures[st.top()]

当前日期不能成为栈顶日期的答案。

因此代码只在：

temperatures[i] > temperatures[st.top()]

时弹栈。

相同温度会继续留在栈中，等待未来真正更高的温度。

为什么初始化答案为 0

代码先创建：

vector<int> ans(n, 0);

只有找到更高温度的日期才会修改对应位置。

如果某个下标直到遍历结束仍在栈中，说明它后面没有更高温度，答案保持初始值 0。

这正好符合题目要求。

边界情况

如果数组只有一天，这一天后面没有温度，答案是：

[0]

如果温度严格递增，例如：

[30,40,50,60]

每到一个新温度，都会解决前一天的等待问题，最后一天没有更高温度，答案为 0。

如果温度严格递减，例如：

[60,50,40,30]

没有任何元素会被弹出，所有答案都保持为 0。

如果存在相同温度，相同温度不会被当成更高温度，只有严格更高的温度才能触发弹栈。

正确性证明

我们证明：算法返回的 answer[i] 正确表示第 i 天之后等待几天可以遇到更高温度。

结论 1：栈中保存的都是还没有找到更高温度的日期

每个日期下标在被扫描到时都会进入栈。

如果之后遇到更高温度，算法就会弹出它并设置对应答案。

如果它一直没有遇到更高温度，就会一直留在栈中。

因此，栈中不会保存已经找到答案的日期，只保存仍在等待更高温度的日期。

结论 2：栈中温度始终保持单调不增

新下标入栈前，算法会不断弹出所有满足：

temperatures[i] > temperatures[st.top()]

的栈顶元素。

弹栈结束后，如果栈不为空，则有：

temperatures[st.top()] >= temperatures[i]

然后把当前下标 i 压入栈顶。

因此从栈底到栈顶的温度仍然保持单调不增。

结论 3：每次弹出的日期都找到了它之后第一个更高温度

设当前扫描到下标 i，并弹出下标 j。

弹出条件说明：

temperatures[i] > temperatures[j]

在扫描到 i 之前，所有位于 j 和 i 之间的日期都已经被处理过，但没有弹出 j。

这说明这些日期的温度都没有严格高于 temperatures[j]，否则 j 早就会被弹出。

所以 i 是 j 之后第一个温度严格高于 temperatures[j] 的日期。

算法设置：

answer[j] = i - j

因此该答案正确。

结论 4：不会漏掉任何有答案的日期

考虑任意一个日期 j。

如果它后面存在更高温度，那么从左到右扫描时，算法最终一定会遇到第一个满足：

temperatures[i] > temperatures[j]

的日期 i。

在此之前，j 不会因为温度不够高而被弹出，也不会被错误删除，因为只有更高温度才能弹出它。

因此扫描到 i 时，j 仍然在栈中，并会被正确弹出并计算答案。

如果它后面不存在更高温度，那么它会一直留在栈中，答案保持为 0，也符合题意。

结论 5：被弹出的日期不会影响后续答案

一个日期 j 被弹出时，已经找到了它之后第一个更高温度。

题目只关心这个日期的第一个更高温度，后面再出现的温度不需要继续考虑。

因此弹出 j 不会影响 answer[j]，也不会影响其他日期的判断。

得出结论

由结论 1 可知，栈中始终保存尚未解决的日期。

由结论 2 可知，栈的单调性始终成立。

由结论 3 可知，每次弹栈计算出的答案都是对应日期之后的第一个更高温度。

由结论 4 可知，所有有答案的日期都会被处理，没有答案的日期会保留 0。

由结论 5 可知，弹出已经解决的日期不会影响后续判断。

因此算法返回的数组正确。

举例理解

以：

temperatures = [73,74,75,71,69,72,76,73]

为例。

遍历结束后，下标 6 和 7 仍在栈中，说明它们后面没有更高温度。

它们的答案保持为 0。

最终得到：

[1,1,4,2,1,1,0,0]

复杂度分析

每个下标最多入栈一次。

每个下标最多出栈一次。

虽然代码中有嵌套的 while，但所有弹栈操作加起来最多执行 n 次。

因此时间复杂度是：

O(n)

答案数组需要 O(n) 空间，单调栈最坏也会保存 O(n) 个下标。

所以空间复杂度是：

O(n)