时间轴

2026-03-18

init

题目：

P739 每日温度

https://leetcode.cn/problems/daily-temperatures/description/?envType=study-plan-v2&envId=top-100-liked

单调栈，栈中元素始终保持单调递减

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <vector>
#include <stack>

using std::vector;
using std::stack;

class Solution {
    public:
        vector<int> dailyTemperatures(vector<int> &temperatures)
        {
                int i, n = temperatures.size();
                vector<int> res(n, 0);
                stack<int> stk; // 单调栈，单调递减

                for (i = 0; i < n; i++) {
                        while (!stk.empty() && temperatures[i] > temperatures[stk.top()]) {
                                res[stk.top()] = i - stk.top();
                                stk.pop();
                        }

                        stk.push(i);
                }

                while (!stk.empty()) {
                        res[stk.top()] = 0;
                        stk.pop();
                }
                res[n - 1] = 0;

                return res;
        }
};

#include <cstdio>
int main()
{
        Solution S;
        vector<int> temperatures = { 73, 74, 75, 71, 69, 72, 76, 73 };
        vector<int> res;

        res = S.dailyTemperatures(temperatures);

        for (int val : res)
                std::printf("%d ", val);

        printf("\n");
}