LeetCode hot 100—每日温度

题目

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

分析

单调栈是一种特殊的数据结构，它可以帮助我们在  O() 的时间复杂度内解决这个问题，其中 是数组的长度。

单调栈

对于每个元素 temperatures[i]：

• 单调栈的处理：当栈不为空且栈顶元素对应的温度小于当前温度时，说明找到了栈顶元素对应的下一个更高温度。此时，弹出栈顶元素 prevIndex，并更新 answer[prevIndex] 为 i - prevIndex，表示距离下一个更高温度的天数。
• 入栈操作：将当前索引 i 压入栈中。

遍历结束后，answer 数组中存储了每个元素对应的下一个更高温度的天数，将其返回。

时间复杂度：O()，  是数组的长度

空间复杂度：O()

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