Daily Temperatures

739. 每日温度

分析

倒序遍历：
- 从最后一天向第一天遍历温度数组
- 因为从后向前，可以快速找到当前温度后面更高的温度
使用单调递减栈：
- 栈中保存数组的下标，保证栈内元素对应的温度单调递减
- 每次遇到更高的温度时，将栈顶元素弹出，更新结果数组
计算结果：
- 如果栈不为空，当前栈顶元素对应的温度是下一个更高温度，计算两者下标的差值
- 如果栈为空，表示后面没有更高温度，结果置为 0
将当前天的下标压入栈，供后续处理

时间复杂度

每个元素最多被压栈和弹栈一次，总时间复杂度 O(n)

空间复杂度

使用了一个栈，最坏情况下栈中可能存储所有天数，空间复杂度为 O(n)

C++代码

 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


class Solution
{
public:
    vector<int> dailyTemperatures(vector<int>& temperatures)
    {
        // 初始化结果数组，长度与输入数组相同，初始值为 0
        std::vector<int> res(temperatures.size());
        // 单调栈，存储下标
        std::stack<int> stk;

        // 从后向前遍历温度数组
        for (int i = temperatures.size() - 1; i >= 0; --i)
        {
            // 弹出所有不满足更高温度条件的栈顶元素
            while (!stk.empty() && temperatures[i] >= temperatures[stk.top()])
                stk.pop();

            // 如果栈不为空，计算下标差值作为结果
            if (!stk.empty())
                res[i] = stk.top() - i;

            // 将当前下标压入栈
            stk.push(i);
        }

        return res;
    }
};