跳至主要內容

单调栈（Monotonic Stack）

老马啸西风2025年10月6日大约 7 分钟Althgorimalthgorimmonotonic-stack

🧩 一、单调栈是什么？

单调栈 是一种特殊的栈结构，它在“栈中元素单调递增或单调递减”这一规则下进行操作。

它不是一种新的数据结构，而是一种 使用栈解决某类问题的技巧。

简单来说：

  • 单调递增栈：栈内元素从栈底到栈顶是递增的（越往上越大）。
  • 单调递减栈：栈内元素从栈底到栈顶是递减的（越往上越小）。

🧠 二、为什么需要单调栈？

在很多算法题中，我们经常遇到这种需求：

对于数组中的每个元素，找出它 左边/右边 第一个比它 大/小 的元素。

例如：

输入: [2, 1, 4, 3]
输出:
  每个元素右边第一个比它大的元素：
  2 -> 4
  1 -> 4
  4 -> 没有
  3 -> 没有

如果暴力做法就是嵌套循环：O(n²)。

而用单调栈，这种问题可以在 O(n) 时间解决。

🧩 三、工作原理（核心思想）

我们以「找右边第一个更大元素」为例来说明：

int[] nextGreaterElements(int[] nums) {
    int n = nums.length;
    int[] res = new int[n];
    Arrays.fill(res, -1);
    Deque<Integer> stack = new ArrayDeque<>(); // 存放下标（索引）

    for (int i = 0; i < n; i++) {
        // 当前元素比栈顶元素大 → 当前元素就是栈顶元素的“下一个更大值”
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            int idx = stack.pop();
            res[idx] = nums[i];
        }
        // 当前索引入栈
        stack.push(i);
    }
    return res;
}

🔍 核心逻辑：

  • 栈中保持的是一个 单调递减栈（栈顶最小）。
  • 当遇到比栈顶大的元素，就能“结算”栈顶。
  • 每个元素最多进出栈一次，所以时间复杂度 O(n)。

⚙️ 四、单调栈的常见类型与应用场景

类型栈中单调性目标常见题目示例
单调递减栈从栈底到栈顶递减找“右边第一个更大值”下一个更大元素、每日温度
单调递增栈从栈底到栈顶递增找“右边第一个更小值”柱状图最大矩形、接雨水
反向遍历 + 单调栈从右往左遍历找“左边第一个更大/更小值”对称类题型

🧮 五、经典题目讲解

🧊 例1：LeetCode 739 — 每日温度

给定一组温度，返回每一天需要等几天才会遇到更高的温度。

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] res = new int[n];
    Deque<Integer> stack = new ArrayDeque<>(); // 存放下标

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int idx = stack.pop();
            res[idx] = i - idx;
        }
        stack.push(i);
    }
    return res;
}

思路：

  • 栈中存放还没有遇到“更高温度”的天数索引。
  • 每遇到更高温度，就更新结果。

🧱 例2：LeetCode 84 — 柱状图中最大矩形

给定每个柱子的高度，找能形成的最大矩形面积。

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    Deque<Integer> stack = new ArrayDeque<>();
    int max = 0;

    for (int i = 0; i <= n; i++) {
        int cur = (i == n ? 0 : heights[i]);
        while (!stack.isEmpty() && cur < heights[stack.peek()]) {
            int h = heights[stack.pop()];
            int left = stack.isEmpty() ? -1 : stack.peek();
            int width = i - left - 1;
            max = Math.max(max, h * width);
        }
        stack.push(i);
    }
    return max;
}

思路：

  • 单调递增栈，用于确定每个柱子“左边第一个更矮的柱子”和“右边第一个更矮的柱子”。
  • 出栈时计算面积。

🌧 例3：LeetCode 42 — 接雨水

利用单调递减栈求“当前高度能形成的水量”。

public int trap(int[] height) {
    int n = height.length, res = 0;
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int mid = stack.pop();
            if (stack.isEmpty()) break;
            int left = stack.peek();
            int width = i - left - 1;
            int h = Math.min(height[left], height[i]) - height[mid];
            res += width * h;
        }
        stack.push(i);
    }
    return res;
}

🧭 六、通用模板总结

for (int i = 0; i < n; i++) {
    while (!stack.isEmpty() && 满足单调性被破坏的条件) {
        // 出栈并处理逻辑
    }
    stack.push(i);
}

根据需求调整：

  • 想找“右边第一个更大”：递减栈
  • 想找“右边第一个更小”：递增栈
  • 想找“左边第一个更大”：反向遍历 + 递减栈
  • 想找“左边第一个更小”：反向遍历 + 递增栈

🎯 七、总结

场景栈类型遍历方向
右边第一个更大单调递减栈从左到右
右边第一个更小单调递增栈从左到右
左边第一个更大单调递减栈从右到左
左边第一个更小单调递增栈从右到左

为什么不能用大小堆来解决这种问题？？

这个问题问得非常好👏，很多人刚学单调栈时都会产生这个疑问：

“既然堆（PriorityQueue）能帮我们快速拿到最大/最小值，那为什么还要用单调栈？”

—— 关键区别在于：单调栈维护的是“相对位置顺序 + 局部单调性”，而堆只维护“整体大小关系”。
我们来仔细拆开说 👇

🧩 一、堆的核心特性

堆（无论最大堆还是最小堆）能在 O(1) 时间找到最大/最小值，
在 O(log n) 时间插入或删除。

但是：

  • 堆中元素是 无序的集合结构；
  • 你只能知道「全局最小 / 最大」是谁；
  • 你 不知道它在数组中的位置；
  • 你也 无法根据顺序快速移除“过期的元素”。

🧠 二、单调栈的核心特性

单调栈是一种 按原数组顺序动态维护“有序局部结构”的工具。

它的本质是：

在遍历数组的过程中，实时记录「当前元素与前面元素之间的顺序关系」。

它保留了索引顺序！
也就是说，单调栈不仅知道谁更大/更小，还知道它们的相对位置（在谁的左边或右边）。

🧮 三、举个对比例子

我们拿经典问题「右边第一个更大元素」来比较。

例子

nums = [2, 1, 4, 3]

我们要得到：

2 -> 4
1 -> 4
4 -> 没有
3 -> 没有

🧱 用堆试试看

假设你遍历到 2，你把它放进最大堆；
遍历到 1，放进去；
遍历到 4，堆顶现在是 4 —— 是的，它是最大值，但：

❌ 你并不知道 4 在 2 的右边还是左边；
❌ 也不知道 4 是不是紧挨着 2 的那个「第一个更大元素」；
❌ 更别提维护多个不同索引之间的关系了。

堆只能告诉你：

“现在我手里最大的数是 4。”

但题目要的是：

“在我后面、距离我最近、比我大的那个数是谁。”

堆没有顺序概念，它无法回答“谁在右边第一个更大”的问题。

🧊 用单调栈来做

单调递减栈的过程如下：

步骤元素栈内容（存索引）出栈/更新情况
i=02[0]
i=11[0,1]
i=24[ ]出栈1→4，出栈0→4
i=33[2,3]

它自动完成了：

  • 比当前小的都被“解决”；
  • 右边第一个更大是谁；
  • 不需要排序、不需要 log n 插入。

👉 每个元素最多进出栈一次，O(n)。

⚖️ 四、总结区别

对比项单调栈堆
数据结构特性保留顺序，局部单调无序，全局堆序
主要用途找“左右第一个更大/更小”找全局最值（最大、最小）
能否知道“相对位置”✅ 可以❌ 不行
时间复杂度O(n)O(n log n)（每次插入 O(log n)）
是否支持“过期元素”快速移除✅ 直接出栈❌ 不行，需懒惰删除或重建堆
常见题目每日温度、接雨水、柱状图最大矩形优先队列、Top K、合并有序流

🧩 五、类比理解

你可以这样记：

  • 堆：像一个「排行榜」，你能随时知道谁最高分，但不知道谁在谁后面。
  • 单调栈：像一个「逐个扫描的观察者」，知道每个元素左边和右边比它大/小的第一个是谁。

🎯 结论

单调栈解决的是 “带有相对位置约束 的比较问题”；

堆解决的是 “只关心全局大小关系 的问题”。

换句话说：

  • “找第一个比我大的” → 单调栈
  • “找所有人里最大的” → 堆

贡献者

bbhou
我是老马，期待与你的下次重逢
Copyright © 2025 老马啸西风