【算法图解】单调栈：解决 Next Greater 问题

你可能做过这种题：

对于数组每个元素，找右边第一个比它大的元素（Next Greater Element）

朴素解法：

对每个元素向右扫描

最坏 $O(n^2)$。

单调栈能把它降到 $O(n)$。

核心直觉：

你不需要把“所有历史元素”都记住，只需要记住“还有机会被未来元素解决”的那些。

1. 什么是单调栈？

单调栈维护一种单调性：

单调递减栈：栈内从栈底到栈顶递减
单调递增栈：栈内从栈底到栈顶递增

很多 Next Greater 类题用单调递减栈：

当你看到一个更大的元素时，它可以“解决”栈顶（以及一串更小的）。

2. Next Greater Element 模板（可运行）

function nextGreater(nums) {
  const res = new Array(nums.length).fill(-1)
  const st = [] // 存索引

  for (let i = 0; i < nums.length; i++) {
    while (st.length && nums[i] > nums[st[st.length - 1]]) {
      const j = st.pop()
      res[j] = nums[i]
    }
    st.push(i)
  }

  return res
}

console.log(nextGreater([2, 1, 2, 4, 3]))
// [4, 2, 4, -1, -1]

为什么是 O(n)？

每个元素最多入栈一次、出栈一次

总操作次数是线性的。

3. 单调栈的两种常见形态

3.1 找右边第一个更大

从左到右扫描
用递减栈

3.2 找左边第一个更小/更大

从左到右扫描
用递增/递减栈（看题意）

也可以反过来从右到左。

4. 典型题：每日温度

题意：每一天要等几天才会更暖。

本质：对每个元素找右边第一个更大元素的“距离”。

function dailyTemperatures(t) {
  const res = new Array(t.length).fill(0)
  const st = []

  for (let i = 0; i < t.length; i++) {
    while (st.length && t[i] > t[st[st.length - 1]]) {
      const j = st.pop()
      res[j] = i - j
    }
    st.push(i)
  }

  return res
}

5. 典型题：柱状图最大矩形（思路版）

这题会用到“找每个柱子左右第一个更小的位置”。

单调递增栈可以在 O(n) 内求出：

左边界
右边界

然后面积就是：

height[i] * (right[i] - left[i] - 1)

（完整代码略长，但核心就是两个边界的单调栈模板。）

6. 面试回答模板

我用单调栈维护一个递减（或递增）序列。
当遇到一个元素打破单调性时，弹栈并结算答案。
每个元素最多入栈出栈一次，因此时间 O(n)，空间 O(n)。

总结

单调栈把“向左/向右找第一个更大/更小”降到 O(n)。
关键是：弹栈时结算，入栈保持单调。
高频题：Next Greater、每日温度、柱状图最大矩形。

【算法图解】单调栈：解决 Next Greater 问题

相关标签