单调栈算法全攻略：从基础模板到机试高阶应用

蔚蓝WEILANX2026-03-042026-03-04

单调栈算法全攻略：从基础模板到机试高阶应用

在算法竞赛和考研机试（尤其是像华东师范大学这样重视算法的学校）中，单调栈（Monotonic Stack） 是一个非常高效的工具。它能将许多看似需要 $O(N^2)$ 遍历的问题，巧妙地优化到 $O(N)$。

本文将从单调栈的底层逻辑出发，带你掌握从基础模板到复杂变体的全套打法。

一、什么时候该想到单调栈？

当你遇到这类描述时，大脑中应当瞬间闪过“单调栈”：

“寻找数组中每个元素左边/右边 第一个 比它大（或小）的元素。”

单调栈的本质：遮蔽与保护

单调栈本质上是在维护一个“可见性”序列。

单调递增栈（从栈底到栈顶）：用于寻找左/右第一个更小的元素。
单调递减栈（从栈底到栈顶）：用于寻找左/右第一个更大的元素。

当一个新元素准备入栈时，如果它破坏了栈的单调性，说明原本在栈里的元素遇到了它们的“克星”（更小或更大的数），此时就是记录答案的最佳时机。

二、算法通用模板 (Java)

机试中推荐使用 ArrayDeque 作为栈的实现，性能优于 Stack。

// 以寻找右侧第一个更大元素为例
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
    // 只要当前元素比栈顶大，就说明找到了栈顶元素的“下一个更大元素”
    while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
        int topIdx = stack.pop();
        ans[topIdx] = nums[i]; // 记录答案
    }
    stack.push(i); // 将当前下标入栈
}

三、典型案例分析

1. 基础应用：每日温度

题目：计算每一个温度到下一个更高温度需要等待的天数。

核心代码：

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] ans = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int prevIndex = stack.pop();
            ans[prevIndex] = i - prevIndex;
        }
        stack.push(i);
    }
    return ans;
}

具体思路：

单调性：我们要找“右侧第一个更大值”，所以维护一个从栈底到栈顶递减的栈。
操作逻辑：遍历温度数组，如果当前温度高于栈顶温度，说明栈顶元素遇到了它的“更暖和的一天”，计算间距后弹出；否则入栈等待。
结果记录：栈中存储的是下标，这样既能通过 temperatures[stack.peek()] 取值，又能计算 i - stack.peek() 的跨度。

注意点：

默认值：如果某天之后再也没有更高的温度，答案应为 0。在 Java 中 new int[n] 默认初始化就是 0，无需额外处理。
栈内容：永远存下标而非数值。

2. 环形处理：下一个更大元素 II

技巧：两倍长度 + 取模。

核心代码：

public int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    Arrays.fill(ans, -1); // 默认找不到
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < 2 * n; i++) {
        int curr = i % n;
        while (!stack.isEmpty() && nums[curr] > nums[stack.peek()]) {
            ans[stack.pop()] = nums[curr];
        }
        if (i < n) stack.push(i); // 只在第一轮入栈
    }
    return ans;
}

具体思路：

模拟成环：不需要真的把数组翻倍（空间浪费），而是通过遍历 0 到 2n-1 次，并使用 i % n 来模拟数组首尾相连。
第一轮入栈：只有在第一轮遍历（i < n）时才需要将下标入栈，第二轮遍历主要是为了给第一轮剩下的“单身汉”寻找可能出现在数组前端的更大值。

注意点：

初始化：由于是循环数组，仍有可能找不到（比如数组最大值），因此初始值应设为 -1。
避免重复：第二轮不再推入新元素，否则逻辑会陷入混乱。

3. 双向边界：接雨水 & 柱状图最大矩形

核心代码（接雨水）：

public int trap(int[] height) {
    int ans = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int mid = stack.pop(); // 凹槽
            if (stack.isEmpty()) break; // 左侧没有墙了
            int left = stack.peek();
            int h = Math.min(height[left], height[i]) - height[mid];
            int w = i - left - 1;
            ans += h * w;
        }
        stack.push(i);
    }
    return ans;
}

具体思路：

横向切割：单调栈处理接雨水是“一层一层的加”。当遇到更高的墙 i 时，弹出 mid（凹槽），此时 stack.peek() 是左边界，i 是右边界，计算它们围成的水槽面积。
哨兵思想（最大矩形专用）：在处理柱状图最大矩形时，为了防止遍历结束后栈内还有残留（说明这些柱子右侧没有更小的了），我们可以在数组尾部人为添加一个高度为 0 的“哨兵”。

注意点：

中间高度：面积计算时要减去 height[mid]，因为它代表已经计算过的底部高度。
空栈判断：出栈后如果栈空了，说明左侧无墙，接不住水，需 break。

四、进阶变体：ECNU2024-排列删除

核心代码：

// 预处理前缀最大值
boolean[] isPrefixMax = new boolean[n + 1];
long maxVal = -1;
for (int i = 1; i <= n; i++) {
    if (p[i] > maxVal) {
        isPrefixMax[i] = true;
        maxVal = p[i];
    }
}

// 单调栈求左侧第一个比自己大的 LGE 下标
int[] L = new int[n + 1];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 1; i <= n; i++) {
    while (!stack.isEmpty() && p[stack.peek()] < p[i]) stack.pop();
    L[i] = stack.isEmpty() ? 0 : stack.peek();
    stack.push(i);
}

// 判定逻辑
if (y > x) out.println("Yes");
else if (isPrefixMax[x]) out.println("No"); // y 在 x 左侧，前缀最大值必等左侧删完
else {
    if (y > L[x] && y < x) out.println("No");
    else out.println("Yes");
}

核心思路：

LGE 的保护作用：非前缀最大值 $x$ 有一个“保护者” $L[x]$。只要它和 $L[x]$ 之间的数消失了，它就能凭条件 2 删掉。
单调栈的角色：在这里，单调栈不是用来直接算面积，而是用来确定 依赖范围。如果 $y$ 落在 $(L[x], x)$ 区间内，它就是必须被清除的“挡路石”。

注意点：

逻辑抽象：机试中难点在于如何把“删除规则”抽象成“单调栈寻找第一个更大元素”的模型。
哨兵值 0：如果左侧没有比自己大的，L[i] 为 0，此时该数即为前缀最大值。

五、总结对照表

场景	栈的单调性	关键触发点
右侧第一个更大	递减 (Top最小)	`nums[i] > stack.peek()`
右侧第一个更小	递增 (Top最大)	`nums[i] < stack.peek()`
左侧第一个更大	递减 (入栈前查找)	`stack.peek()` 即为答案
滑动窗口极值	(单调队列)	头部失效 + 尾部维护单调