Medium

题目描述

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

解题思路

这道题是经典的单调栈应用问题，需要找到每个位置右边第一个比它大的元素。

思路分析：

最直观的方法是暴力枚举，对于每个位置 i，向右遍历找到第一个比 temperatures[i] 大的元素。但这种方法时间复杂度为 O(n²)，在数据规模较大时会超时。

单调栈解法（推荐）： 使用单调递减栈来优化。栈中存储数组的下标，维护从栈底到栈顶温度递减的性质：

  1. 遍历数组，对于当前元素 temperatures[i]
  2. 如果栈不为空且当前温度大于栈顶下标对应的温度，说明找到了栈顶位置的答案
  3. 弹出栈顶，计算天数差值，直到栈为空或当前温度不大于栈顶温度
  4. 将当前下标入栈

这样每个元素最多入栈出栈一次，时间复杂度降为 O(n)。

其他解法： 还可以从右往左遍历，利用温度范围有限的特点，但单调栈是最通用和高效的解法。

代码实现

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

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        result = [0] * n
        stack = []
        
        for i in range(n):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                idx = stack.pop()
                result[idx] = i - idx
            stack.append(i)
        
        return result

public class Solution {
    public int[] DailyTemperatures(int[] temperatures) {
        int n = temperatures.Length;
        int[] result = new int[n];
        Stack<int> stack = new Stack<int>();
        
        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && temperatures[i] > temperatures[stack.Peek()]) {
                int idx = stack.Pop();
                result[idx] = i - idx;
            }
            stack.Push(i);
        }
        
        return result;
    }
}

var dailyTemperatures = function(temperatures) {
    const n = temperatures.length;
    const result = new Array(n).fill(0);
    const stack = [];
    
    for (let i = 0; i < n; i++) {
        while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
            const idx = stack.pop();
            result[idx] = i - idx;
        }
        stack.push(i);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n) - 每个元素最多入栈出栈一次
空间复杂度O(n) - 栈的空间开销，最坏情况存储所有元素

相关题目