每日温度

题意

给定每日温度数组，对每一天找出下一个更高温度出现在几天后。

思路

从左到右扫描，维护单调栈（从栈底到栈顶温度递减）。栈中保存尚未遇到更高温度的下标：

当前温度 temps[i] 比栈顶温度高时，栈顶位置找到了答案：answer[st.top()] = i - st.top()，弹出栈顶。
重复直到栈顶温度不低于当前，然后压入当前下标。

扫描结束后栈中剩余的下标没有更高温度，答案保持 0。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32#include <bits/stdc++.h>
using namespace std;

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    for (int x : Solution().dailyTemperatures(a))
        cout << x << ' ';
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#!/usr/bin/env python3
from typing import List


class Solution:
    def dailyTemperatures(self, temps: List[int]) -> List[int]:
        n = len(temps)
        ans = [0] * n
        st = []
        for i in range(n):
            while st and temps[st[-1]] < temps[i]:
                ans[st.pop()] = i - st[-1]
            st.append(i)
        return ans


def main():
    n = int(input())
    a = list(map(int, input().split()))
    print(*Solution().dailyTemperatures(a))


if __name__ == "__main__":
    main()

复杂度

时间复杂度： $O(n)$ ，每个下标最多入栈、出栈一次。
空间复杂度： $O(n)$ ，栈最多存所有下标。

总结

单调栈的核心是"栈中保存尚未解决的候选"，遇到更大的值时逐个结算。本题栈存下标而非值，弹出时用下标差计算距离。

目录

题意

思路

代码

复杂度

总结