vvrf / DSA.log

问题拆解

给定每天的温度 temperatures，对每一天回答：还要等几天才会出现更高的温度？等不到就填 0。

朴素做法是对每个 i 向右扫描，找到第一个比它高的温度，最坏 O(n²)——温度整体递减时每次都要扫到底。浪费在哪里？向右扫描时读到的信息全被扔掉了：明明已经知道中间这些天都不比 temperatures[i] 暖，换下一个起点又要重看一遍。

换个方向想：当第 i 天的温度到来时，它能一次性回答掉之前所有温度比它低、还没有答案的日子。所以我维护一个“悬而未决”的下标栈，栈里对应的温度从底到顶递减；新温度更高时不断弹栈结算，直到栈顶不再比它低，然后自己入栈继续等。

单调栈的本质：栈里存的是“还没等到答案的问题”，每个新元素先扮演答案，把能解决的都解决掉，再变成新的问题入栈。

递减栈存下标，新高温负责结算

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] answer = new int[n];
    Deque<Integer> stack = new ArrayDeque<>(); // 存下标，对应温度从底到顶递减
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int j = stack.pop();
            answer[j] = i - j; // 第 i 天就是第 j 天等到的更暖日
        }
        stack.push(i);
    }
    return answer;
}

def dailyTemperatures(temperatures: List[int]) -> List[int]:
    answer = [0] * len(temperatures)
    stack = []  # 存下标，对应温度从底到顶递减

    for i, t in enumerate(temperatures):
        while stack and t > temperatures[stack[-1]]:
            j = stack.pop()
            answer[j] = i - j  # 第 i 天就是第 j 天等到的更暖日
        stack.append(i)

    return answer

func dailyTemperatures(temperatures []int) []int {
    answer := make([]int, len(temperatures))
    stack := []int{} // 存下标，对应温度从底到顶递减
    for i, t := range temperatures {
        for len(stack) > 0 && t > temperatures[stack[len(stack)-1]] {
            j := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            answer[j] = i - j // 第 i 天就是第 j 天等到的更暖日
        }
        stack = append(stack, i)
    }
    return answer
}

pub fn daily_temperatures(temperatures: Vec<i32>) -> Vec<i32> {
    let mut answer = vec![0; temperatures.len()];
    let mut stack: Vec<usize> = Vec::new(); // 存下标，对应温度从底到顶递减
    for (i, &t) in temperatures.iter().enumerate() {
        while stack.last().map_or(false, |&j| temperatures[j] < t) {
            let j = stack.pop().unwrap();
            answer[j] = (i - j) as i32; // 第 i 天就是第 j 天等到的更暖日
        }
        stack.push(i);
    }
    answer
}

两个细节最容易错：一是栈里必须存下标而不是温度，因为答案要的是“隔了几天”（i - j），温度随时能用下标查回来，反过来不行；二是弹栈条件必须严格大于——温度相等不算“更暖”，弹了就是错的。

再看为什么是 O(n)：外层循环走 n 次，内层 while 看似又是一层循环，但每次弹栈消耗的都是历史上入过栈的元素。每个下标恰好入栈一次、至多出栈一次，所有 while 加起来的总弹栈次数不超过 n，整体是均摊 O(n)，而不是表面上的 O(n²)。

复杂度

指标	复杂度	原因
时间	`O(n)`	每个下标入栈一次、出栈至多一次，总操作数被 2n 封顶
空间	`O(n)`	温度单调递减时栈里会压着全部下标

可以迁移的模式

“下一个更大 / 更小元素”这一族问题，几乎都是单调栈的直接应用；
分析嵌套循环别只看形状，看“每个元素总共被处理几次”——均摊分析常把表面的 O(n²) 拉回 O(n)；
栈里存下标不存值：下标能换回值，还能算距离。

当暴力解法在反复扫描已经看过的区间时，就该想想能不能用一个单调结构把这些信息暂存下来。