04 单调栈入门：每日温度与下一个更大元素

单调栈入门：每日温度与下一个更大元素

摘要

单调栈（Monotonic Stack）是本专栏最重要的技术，也是算法面试中性价比最高的知识点之一：模板固定、代码量少、能解决大量”下一个更大/更小元素”、“左右边界”等范围查询问题。本篇通过三道题系统建立单调栈的直觉：LeetCode 739（每日温度）是标准入门题，建立”维护递减栈，遇到更大元素触发弹栈”的核心思维模式；LeetCode 496（下一个更大元素 I）引入了”两个数组的映射”变体；LeetCode 503（下一个更大元素 II）引入了”循环数组”的处理技巧。三道题一气呵成，彻底打通单调栈的基础用法。

---

第 1 章 单调栈的直觉来源

1.1 从朴素暴力说起

LeetCode 739 问题：给定一个整数数组 temperatures，表示每天的气温，返回一个数组 answer，其中 answer[i] 是第 i 天之后（比较严格地说：至少需要等多少天）才能等到一个更暖和的气温。如果气温在这之后都不会升高，在该位置用 0 来代替。

temperatures = [73,74,75,71,69,72,76,73]
answer       = [1, 1, 4, 2, 1, 1, 0, 0]

朴素暴力解法：对每天 i，向右扫描找到第一个 temperatures[j] > temperatures[i]，answer[i] = j - i。

// 暴力 O(n²)
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (temperatures[j] > temperatures[i]) {
            answer[i] = j - i;
            break;
        }
    }
}

时间 $O(n^2)$，$n=10^5$ 时会超时。

1.2 单调栈的核心洞察

问题本质：对每个元素 i，找到它右边第一个比它大的元素的位置。

关键观察：当我们从左往右扫描时，一个元素的”下一个更大元素”是什么时候才能确定？当我们第一次遇到一个比它更大的元素时。

换句话说，元素 i 的答案需要等到未来的某个时刻 j（temperatures[j] > temperatures[i]）才能被”解锁”。在 j 到来之前，元素 i 是”悬而未决”的，需要暂时保存起来。

用什么保存悬而未决的元素？栈！——因为越晚加入的元素，越先被”更大元素”所解锁（后进的元素在右边更近，更容易遇到更大的值）。

单调栈的规则（递减栈，用于寻找”下一个更大元素”）：

1. 遍历到元素 i 时，不断弹出栈中所有小于 temperatures[i] 的元素（弹出的元素找到了答案：答案就是 i）
2. 最后将 i 压入栈

遍历结束后，栈中剩余的元素是找不到更大值的（答案为 0）。

由于栈中始终保持”从底到顶单调递减”，所以叫单调递减栈（Monotone Decreasing Stack）。

---

第 2 章 LeetCode 739：每日温度

2.1 题目

LeetCode 739 - Daily Temperatures（中等）

给定一个整数数组 temperatures，表示每天的气温，返回 answer[i] 为第 i 天后，至少需要等几天才能看到更高的气温。如果气温在此之后都不会升高，在该位置用 0 来代替。

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

2.2 代码实现

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] answer = new int[n]; // 默认值 0（找不到更大值的情况）
    
    // 单调递减栈：存储"悬而未决"的下标
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int i = 0; i < n; i++) {
        // 当前温度 temperatures[i] 大于栈顶温度
        // → 栈顶的元素找到了它的"下一个更大值"
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int prev = stack.pop();
            answer[prev] = i - prev; // 等待的天数
        }
        stack.push(i); // 压入当前下标（不是温度！）
    }
    
    // 栈中剩余元素：找不到更大值，answer 保持默认 0
    return answer;
}

2.3 逐步模拟

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
indices       [ 0,  1,  2,  3,  4,  5,  6,  7]

i=0, t=73: 栈空，直接压 → stack=[0]
i=1, t=74: 74>73（stack.peek()=0→t[0]=73）
  弹出 0, answer[0]=1-0=1
  74 无法弹出更多（栈空），压入 1 → stack=[1]
i=2, t=75: 75>74（t[1]=74）
  弹出 1, answer[1]=2-1=1
  栈空，压入 2 → stack=[2]
i=3, t=71: 71<75（t[2]=75），不弹，压入 3 → stack=[2,3]
i=4, t=69: 69<71（t[3]=71），不弹，压入 4 → stack=[2,3,4]
i=5, t=72: 
  72>69（t[4]=69），弹出 4, answer[4]=5-4=1
  72>71（t[3]=71），弹出 3, answer[3]=5-3=2
  72<75（t[2]=75），停止弹出
  压入 5 → stack=[2,5]
i=6, t=76:
  76>72（t[5]=72），弹出 5, answer[5]=6-5=1
  76>75（t[2]=75），弹出 2, answer[2]=6-2=4
  栈空，压入 6 → stack=[6]
i=7, t=73: 73<76（t[6]=76），压入 7 → stack=[6,7]

遍历结束，stack=[6,7]，answer[6]=answer[7]=0（保持默认）

最终: answer = [1,1,4,2,1,1,0,0] ✓

复杂度：时间 $O(n)$，空间 $O(n)$。

为什么时间是 $O(n)$？ 每个元素最多被压栈一次，弹栈一次。虽然内层 while 循环看起来可能多次执行，但总弹栈次数不超过 $n$（每个元素只弹一次），所以总时间是 $O(n)$（摊还分析）。

---

第 3 章 LeetCode 496：下一个更大元素 I

3.1 题目

LeetCode 496 - Next Greater Element I（简单）

给你两个没有重复元素的数组 nums1 和 nums2，其中 nums1 是 nums2 的子集。

请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。

nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置右侧的第一个比 x 大的元素。如果不存在，对应位置输出 -1。

输入: nums1 = [4,1,2], nums2 = [1,3,4,2]
输出: [-1,3,-1]
解释:
  对于 nums1[0]=4，在 nums2 中，4 右边没有比 4 大的 → -1
  对于 nums1[1]=1，在 nums2 中，1 右边第一个更大的是 3 → 3
  对于 nums1[2]=2，在 nums2 中，2 右边没有比 2 大的 → -1

3.2 思路分析

暴力做法：对 nums1 中的每个元素，在 nums2 中找到其位置，再向右扫描找第一个更大值。时间 $O(m\cdot n)$。

单调栈优化：先对 nums2 用单调栈，求出 nums2 中每个元素的”下一个更大元素”，结果存入哈希表（value → nextGreater）。再遍历 nums1，直接从哈希表查询。

public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    // 第一步：对 nums2 用单调栈，建立 value → nextGreater 的映射
    Map<Integer, Integer> nextGreater = new HashMap<>();
    Deque<Integer> stack = new ArrayDeque<>(); // 存储值（不是下标，因为 nums2 元素无重复）
    
    for (int num : nums2) {
        // 当前 num 大于栈顶 → 栈顶找到了 nextGreater
        while (!stack.isEmpty() && num > stack.peek()) {
            nextGreater.put(stack.pop(), num);
        }
        stack.push(num);
    }
    // 栈中剩余元素：nextGreater 不存在，默认 -1
    while (!stack.isEmpty()) {
        nextGreater.put(stack.pop(), -1);
    }
    
    // 第二步：对 nums1 中的每个元素查表
    int[] result = new int[nums1.length];
    for (int i = 0; i < nums1.length; i++) {
        result[i] = nextGreater.get(nums1[i]);
    }
    return result;
}

手动验证（nums2 = [1,3,4,2]）：

遍历 nums2:
num=1: 栈空，压 1 → stack=[1]
num=3: 3>1，弹 1, nextGreater[1]=3
       栈空，压 3 → stack=[3]
num=4: 4>3，弹 3, nextGreater[3]=4
       栈空，压 4 → stack=[4]
num=2: 2<4，直接压 → stack=[4,2]

剩余处理:
弹 2, nextGreater[2]=-1
弹 4, nextGreater[4]=-1

nextGreater = {1:3, 3:4, 4:-1, 2:-1}

查询 nums1=[4,1,2]:
  4 → -1 ✓
  1 → 3 ✓
  2 → -1 ✓

复杂度：时间 $O(m+n)$，空间 $O(n)$（哈希表）。

---

第 4 章 LeetCode 503：下一个更大元素 II（循环数组）

4.1 题目

LeetCode 503 - Next Greater Element II（中等）

给定一个循环数组 nums（nums[nums.length - 1] 的下一个元素是 nums[0]），返回 nums 中每个元素的下一个更大元素。

输入: nums = [1,2,1]
输出: [2,-1,2]
解释:
  1 的下一个更大值是 2
  2 的下一个更大值不存在，返回 -1
  1 的下一个更大值是 2（循环，找到了 nums[1]=2）

4.2 处理循环数组的技巧

循环数组问题的标准处理方式：遍历两遍（或等价地，将数组长度视为 2n，下标用取模处理）。

直觉：循环数组中，任何元素最多向右看 n-1 步就能找到下一个更大元素（或确认不存在）。遍历两遍，第一遍找右边的，第二遍找”绕回来”的。

public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1); // 默认 -1（找不到更大值）
    
    Deque<Integer> stack = new ArrayDeque<>(); // 存下标
    
    // 遍历 2n 次，下标取模模拟循环
    for (int i = 0; i < 2 * n; i++) {
        int idx = i % n; // 实际数组下标
        int num = nums[idx];
        
        while (!stack.isEmpty() && num > nums[stack.peek()]) {
            int prev = stack.pop();
            result[prev] = num;
        }
        
        // 只在第一遍时压栈（第二遍无需再压，避免重复）
        if (i < n) {
            stack.push(idx);
        }
    }
    
    // 栈中剩余元素：已经被 Arrays.fill 设为 -1
    return result;
}

手动验证（nums = [1,2,1]）：

result 初始: [-1,-1,-1]

i=0, idx=0, num=1: 栈空，压 0 → stack=[0]
i=1, idx=1, num=2: 2>1（nums[0]=1），弹 0, result[0]=2
                   栈空，压 1 → stack=[1]
i=2, idx=2, num=1: 1<2（nums[1]=2），压 2 → stack=[1,2]

i=3, idx=0, num=1: 1<2（nums[2]=1，不对，stack.peek()=2，nums[2]=1），
  wait: nums[stack.peek()]=nums[2]=1，1 不大于 1（不严格大），不弹
  i>=n=3，不压栈

i=4, idx=1, num=2: 2>1（nums[stack.peek()=2]=1），弹 2, result[2]=2
                   2 不大于 2（nums[1]=2），不弹
                   i>=n，不压栈

i=5, idx=2, num=1: 1<2（nums[stack.peek()=1]=2），不弹
                   i>=n，不压栈

栈中剩余: [1]，result[1] 保持 -1

最终: result = [2,-1,2] ✓

复杂度：时间 $O(n)$，空间 $O(n)$。

为什么第二遍不需要压栈？

第二遍的目的是让第一遍中”悬而未决”的元素有机会找到循环回来的更大值。第一遍中已经压入的下标，在第二遍中只需要被弹出（找答案），不需要再重复压入（否则会重复计算）。如果 i >= n 时还压栈，会导致同一个下标被压入两次，result 被错误覆盖。

4.3 另一种写法：真正的两遍遍历

部分人觉得 2n 下标不直观，可以写成两个独立的 for 循环：

public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    
    // 第一遍：正常单调栈
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    
    // 第二遍：处理"绕一圈"的情况
    // 此时栈中还有未找到答案的元素
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            result[stack.pop()] = nums[i];
        }
        // 第二遍不压栈
    }
    
    return result;
}

两种写法等价，选哪种取决于个人风格。

---

第 5 章 单调栈的统一模板

通过三道题，我们可以总结出单调栈的统一思维框架：

5.1 问题类型识别

单调栈适用的问题特征：对数组中每个元素，找到右边（或左边）第一个满足某个大小关系的元素。

问题类型	栈的类型	弹栈条件
下一个更大元素	单调递减栈（从底到顶）	当前元素 > 栈顶元素
下一个更小元素	单调递增栈（从底到顶）	当前元素 < 栈顶元素
上一个更大元素（向左找）	从右向左遍历 + 单调递减栈	当前元素 > 栈顶元素
左右两侧边界（同时）	两次单调栈扫描	分别处理

5.2 代码模板

// 求每个元素的"下一个更大元素"（单调递减栈）
Deque<Integer> stack = new ArrayDeque<>(); // 存下标
 
for (int i = 0; i < n; i++) {
    while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
        int idx = stack.pop();
        // 对 idx 位置的元素进行结算：它的下一个更大值是 nums[i]，位置差是 i - idx
        result[idx] = nums[i]; // 或 i - idx 或其他计算
    }
    stack.push(i); // 压入当前下标
}
 
// 处理栈中剩余（找不到更大值的元素）
while (!stack.isEmpty()) {
    result[stack.pop()] = -1; // 或 0，视题意
}

5.3 变体快查

变体	修改点
存值而非下标	无重复元素时可以存值（496 的解法）；有重复元素必须存下标
循环数组	遍历 2n，下标 % n 处理
从右往左扫描	遍历方向反转，用于寻找”上一个更大”
求左右两侧边界（84 题）	两次扫描，或在弹栈时同时计算左右边界

---

下一篇预告

05 单调栈进阶：柱状图中最大矩形 将挑战单调栈最难的应用：LeetCode 84（Largest Rectangle in Histogram，柱状图中最大的矩形）和 LeetCode 85（Maximal Rectangle，最大矩形）。LeetCode 84 要求对每根柱子计算”以它为高度能向左右延伸多远”，本质是用单调递增栈同时维护左右边界；LeetCode 85 则在 84 的基础上，把二维矩阵的每一行都转化为一个柱状图，逐行调用 84 的解法。这两道题是单调栈中最能考验综合运用能力的题目。