算法篇 ｜ 单调栈

前言

在前面的章节中，我们学习了双指针、滑动窗口、二分法这些常用技巧。这一章我们来聊一个相对”小众”但在特定问题上威力巨大的数据结构——单调栈（Monotone Stack）。

单调栈解决的核心问题是：对数组中的每个元素，找到它左边/右边第一个比它大（或小）的元素。 如果用暴力做法，每个元素都要往两边扫，时间复杂度是 O(n²)。单调栈能把这个问题优化到 O(n)。

你可能觉得”找下一个更大元素”这种问题很抽象，实际上它在很多场景中都会出现：

• 股票价格分析——下一个价格更高的交易日是哪天？
• 温度预报——距离下一个更暖和的日子还有几天？
• 直方图面积——柱状图中最大的矩形面积是多少？

本章我们会从单调栈的定义和原理讲起，给出通用模板，然后通过三道经典 LeetCode 题目帮你把这个技巧彻底练熟。

诊断自测

Q1：给定数组 [73, 74, 75, 71, 69, 72, 76, 73]，对每一天，求需要等几天才能等到更高的温度。你会怎么做？

Q2：单调栈为什么能把 O(n²) 优化到 O(n)？

一、单调栈的定义与原理

1.1 什么是单调栈？

单调栈是一个栈内元素保持单调递增或单调递减的栈。

• 单调递增栈（栈底到栈顶递增）：用于找下一个更小的元素
• 单调递减栈（栈底到栈顶递减）：用于找下一个更大的元素

注意：这里的”单调递增/递减”指的是从栈底到栈顶的顺序。有些文章用的是相反的定义，读题时要留意。

1.2 核心原理

以”找每个元素右边第一个比它大的元素”为例：

1. 从左到右遍历数组
2. 对于每个新元素，检查它是否比栈顶元素大
3. 如果大于栈顶元素，说明栈顶元素的”下一个更大元素”就是当前元素。弹出栈顶，记录结果
4. 重复步骤 3 直到栈为空或栈顶元素不小于当前元素
5. 把当前元素入栈

为什么这是对的？ 栈中存的是那些”还没找到下一个更大元素”的元素。当一个更大的元素出现时，它就是所有比它小的栈内元素的答案。

1.3 通用模板

// 找每个元素右边第一个比它大的元素
function nextGreaterElement(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1); // -1 表示没有更大的元素
  const stack = []; // 栈中存放下标

  for (let i = 0; i < n; i++) {
    // 当栈不为空，且当前元素 > 栈顶元素
    while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
      const topIndex = stack.pop();
      result[topIndex] = nums[i]; // 栈顶元素的下一个更大元素就是 nums[i]
    }
    stack.push(i);
  }

  return result;
}

// 示例
nextGreaterElement([2, 1, 2, 4, 3]);
// 结果: [4, 2, 4, -1, -1]

栈中存下标还是值？ 一般存下标，因为下标包含的信息更多——既能通过 nums[index] 获取值，又能计算距离差。

二、经典题目

2.1 每日温度（LeetCode 739）

给定一个每日温度列表 temperatures，对于每一天，计算需要等几天才能等到更高的温度。如果之后没有更高温度的日子，填 0。

这是单调栈最经典的入门题。

function dailyTemperatures(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 topIndex = stack.pop();
      result[topIndex] = i - topIndex; // 等待的天数 = 下标差
    }
    stack.push(i);
  }

  return result;
}

遍历过程（以 [73, 74, 75, 71, 69, 72, 76, 73] 为例）：

i=0: 栈空，push(0)。栈: [0(73)]
i=1: 74 > 73，pop(0)，result[0]=1。push(1)。栈: [1(74)]
i=2: 75 > 74，pop(1)，result[1]=1。push(2)。栈: [2(75)]
i=3: 71 < 75，push(3)。栈: [2(75), 3(71)]
i=4: 69 < 71，push(4)。栈: [2(75), 3(71), 4(69)]
i=5: 72 > 69，pop(4)，result[4]=1。72 > 71，pop(3)，result[3]=2。72 < 75。push(5)。栈: [2(75), 5(72)]
i=6: 76 > 72，pop(5)，result[5]=1。76 > 75，pop(2)，result[2]=4。push(6)。栈: [6(76)]
i=7: 73 < 76，push(7)。栈: [6(76), 7(73)]

遍历结束，栈中剩余元素的 result 保持为 0。
结果: [1, 1, 4, 2, 1, 1, 0, 0]

复杂度分析：

• 时间复杂度：O(n)，每个元素最多入栈出栈各一次
• 空间复杂度：O(n)

2.2 下一个更大元素 I（LeetCode 496）

给定两个没有重复元素的数组 nums1 和 nums2，其中 nums1 是 nums2 的子集。对于 nums1 中的每个元素，找到该元素在 nums2 中对应的下一个更大元素。

function nextGreaterElement(nums1, nums2) {
  const map = new Map(); // 记录 nums2 中每个元素的下一个更大元素
  const stack = [];

  // 先对 nums2 做单调栈，得到每个元素的下一个更大元素
  for (let i = 0; i < nums2.length; i++) {
    while (stack.length > 0 && nums2[i] > stack[stack.length - 1]) {
      map.set(stack.pop(), nums2[i]);
    }
    stack.push(nums2[i]);
  }

  // nums1 中每个元素查询结果
  return nums1.map(num => map.get(num) ?? -1);
}

这道题的变体：栈中直接存值而不是下标，因为题目保证元素不重复，值可以唯一标识元素。

复杂度分析：

• 时间复杂度：O(m + n)
• 空间复杂度：O(n)

2.3 柱状图中最大的矩形（LeetCode 84）

给定 n 个非负整数表示柱状图中每个柱子的高度，找出柱状图中能勾勒出的最大矩形面积。

这是单调栈最经典也最有难度的题目。面试中出现频率很高。

核心思路：对于每个柱子，以它的高度为矩形的高，向左右扩展，直到遇到比它矮的柱子。矩形面积 = 高度 * 宽度。

用单调栈可以高效地找到每个柱子左边第一个比它矮的位置和右边第一个比它矮的位置。

function largestRectangleArea(heights) {
  const n = heights.length;
  const stack = []; // 单调递增栈（栈底到栈顶递增）
  let maxArea = 0;

  // 在末尾加一个 0，确保所有柱子都会被弹出
  heights.push(0);

  for (let i = 0; i <= n; i++) {
    while (
      stack.length > 0 &&
      heights[i] < heights[stack[stack.length - 1]]
    ) {
      const height = heights[stack.pop()];
      // 宽度 = 右边界(i) - 左边界(栈顶+1) = i - stack[top] - 1
      const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }

  heights.pop(); // 恢复原数组

  return maxArea;
}

理解宽度的计算：

当柱子 heights[topIndex] 被弹出时：

• 右边界：当前元素 i（第一个比它矮的右边柱子）
• 左边界：弹出后的新栈顶（第一个比它矮的左边柱子）
• 宽度 = i - stack[top] - 1
• 如果栈为空，说明左边没有更矮的柱子，左边界是 -1，宽度 = i

为什么末尾加一个 0？ 确保遍历结束后栈中所有剩余元素都会被弹出。否则，如果数组本身是递增的（如 [1, 2, 3, 4]），栈中的元素永远不会被弹出，就无法计算面积。

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

三、单调栈的变体总结

记忆技巧：

• 找”更大”用递减栈（栈中维护的是”未被解决的”更大值候选）
• 找”更小”用递增栈
• 找”右边”从左往右遍历
• 找”左边”从右往左遍历

四、单调栈 vs 其他技巧

什么时候该想到单调栈？

1. 题目关键词：下一个更大/更小、距离最近的更大/更小、左右边界
2. 暴力做法是 O(n²) 的嵌套循环：外层遍历每个元素，内层往一个方向扫描找第一个满足条件的元素
3. 需要同时知道左右两边的边界：比如柱状图最大矩形

如果你的暴力思路是”对每个元素，向右扫描找第一个 > 它的”，那就是单调栈的标准应用场景。

常见误区

误区一：“单调栈就是栈里的元素排好序”

单调栈确实保持栈内元素的单调性，但它不是对原数组排序。单调栈的核心价值不在于”排序”，而在于利用单调性快速找到”最近的更大/更小元素”。新元素入栈时，会弹出所有违反单调性的元素，弹出的过程就是在”解决”这些元素的问题。

误区二：“单调栈只能处理一个方向”

通过两次遍历（一次从左到右，一次从右到左），或者通过在末尾加哨兵值，可以同时找到每个元素的左右边界。柱状图最大矩形就是这样——一次遍历中，弹出时自然就得到了左右两个边界。

误区三：“栈中存值就够了”

大多数情况下，栈中应该存下标而不是值。因为很多题目需要计算”距离”（比如每日温度需要知道等了几天），只有存下标才能算出距离。存值的情况很少，通常只在元素不重复且只需要知道”是哪个值”的时候。

误区四：“单调栈的空间复杂度一定是 O(n)”

最坏情况下（数组本身就是单调的），栈中会存放所有元素，空间复杂度确实是 O(n)。但这已经是最优的了——因为我们至少需要遍历每个元素一次。实际上，单调栈的空间通常远小于 n，因为元素会不断被弹出。

小结

单调栈是一个专门用来解决”找最近的更大/更小元素”的利器。虽然应用场景相对集中，但一旦识别出来，就能把 O(n²) 的暴力搜索优化到 O(n)。

核心要点

1. 单调栈的定义：栈内元素保持单调递增或递减
2. 核心操作：新元素入栈时，弹出所有违反单调性的元素并处理它们
3. 时间复杂度 O(n)：每个元素最多入栈一次、出栈一次
4. 栈中存下标：既能获取值，又能计算距离
5. 应用场景：下一个更大/更小元素、温度问题、柱状图矩形

本章思维导图

练习挑战

第一题 ⭐：下一个更大元素 II（LeetCode 503）

给定一个循环数组，输出每个元素的下一个更大元素。循环意味着最后一个元素的下一个元素是第一个元素。

// 示例
// 输入: [1, 2, 1]
// 输出: [2, -1, 2]（最后一个 1 的下一个更大元素是第一个位置的 2）

function nextGreaterElements(nums) {
  const n = nums.length;
  const result = new Array(n).fill(-1);
  const stack = [];

  // 遍历两遍数组来处理循环
  for (let i = 0; i < 2 * n; i++) {
    const index = i % n;

    while (
      stack.length > 0 &&
      nums[index] > nums[stack[stack.length - 1]]
    ) {
      result[stack.pop()] = nums[index];
    }

    // 只在第一遍时入栈
    if (i < n) {
      stack.push(index);
    }
  }

  return result;
}

第二题 ⭐⭐：接雨水（LeetCode 42）— 单调栈解法

给定 n 个非负整数表示柱子的高度，计算能接多少雨水。（这道题在双指针章也出现过，这里用单调栈解。）

function trap(height) {
  const stack = []; // 单调递减栈
  let water = 0;

  for (let i = 0; i < height.length; i++) {
    while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
      const bottom = stack.pop(); // 凹槽的底部

      if (stack.length === 0) break; // 左边没有柱子了

      const left = stack[stack.length - 1]; // 凹槽的左边界
      const width = i - left - 1;
      const h = Math.min(height[left], height[i]) - height[bottom];
      water += width * h;
    }
    stack.push(i);
  }

  return water;
}

第三题 ⭐⭐⭐：最大矩形（LeetCode 85）

给定一个仅包含 0 和 1 的二维矩阵，找出只包含 1 的最大矩形的面积。

function maximalRectangle(matrix) {
  if (matrix.length === 0) return 0;

  const m = matrix.length;
  const n = matrix[0].length;
  const heights = new Array(n).fill(0);
  let maxArea = 0;

  for (let i = 0; i < m; i++) {
    // 更新每一列的高度（连续 1 的个数）
    for (let j = 0; j < n; j++) {
      heights[j] = matrix[i][j] === '1' ? heights[j] + 1 : 0;
    }

    // 对当前行的 heights 调用柱状图最大矩形
    maxArea = Math.max(maxArea, largestRectangleArea(heights));
  }

  return maxArea;
}

function largestRectangleArea(heights) {
  const stack = [];
  let maxArea = 0;
  const h = [...heights, 0]; // 末尾加哨兵

  for (let i = 0; i < h.length; i++) {
    while (stack.length > 0 && h[i] < h[stack[stack.length - 1]]) {
      const height = h[stack.pop()];
      const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
      maxArea = Math.max(maxArea, height * width);
    }
    stack.push(i);
  }

  return maxArea;
}

自我检测

• 能解释单调栈的定义和核心操作（新元素入栈时弹出违反单调性的元素）
• 能默写单调栈的通用模板
• 能说清楚单调递增栈和单调递减栈分别用于什么场景
• 能用单调栈解决”每日温度”问题，并手动模拟遍历过程
• 能用单调栈解决”柱状图中最大的矩形”，并解释宽度的计算方式
• 能解释”末尾加哨兵值”这个技巧的作用
• 能区分栈中存下标和存值的适用场景
• 遇到”找下一个更大/更小元素”类问题时，能立刻想到单调栈