从单调栈面试题延伸：单调栈和单调队列，各解决哪类最值问题

图 1：本文封面，单调栈定边界与单调队列管窗口两个场景的速写。

同批的真题复盘用单调栈解了「区间最小值 × 区间和」那道笔试题，把那道题的推导讲透了。这篇把镜头拉远：单调栈还有个兄弟叫单调队列，两者名字像、都靠「单调性」吃饭，管的却是两类不同的最值问题。搞清楚「哪类问题用哪个结构」，比背任何模板都重要。

两种结构，各维护一条单调不变量。

单调栈维护的是：栈内元素从栈底到栈顶保持单调（递减或递增）。新元素会破坏单调性时，就把栈顶一直弹到不破坏为止——关键在弹出瞬间：被弹出的元素恰好在此刻获得自己的答案。

单调队列维护的是：一个双端队列，队内下标递增、对应的值单调（比如递减），队首永远是当前窗口的最值。它比栈多管一件事——下标滑出窗口的元素要从队首删掉，这是「窗口」语义带来的。

一句话分工：单调栈回答「每个元素的边界在哪」，单调队列回答「每个窗口的最值是谁」。

单调栈的典型问题：下一个更大元素。

以数组 2、1、4、3 为例，维护一个从栈底到栈顶递减的栈：2 入栈得 [2]；1 比栈顶小，直接入栈得 [2,1]；4 来了，它比栈顶的 1 大、比 2 也大，于是 1 和 2 依次弹出——它们遇到的下一个更大元素都是 4；4 入栈后 3 入栈得 [4,3]。扫描结束，栈里剩下的 4 和 3 右侧没有更大元素，记 -1。最终结果 4、4、-1、-1。

为什么敢把弹出的元素「结案」？因为栈递减时，第一个让栈顶站不住的新元素，就是栈顶元素右侧第一个比它大的值——单调性保证了没有更早的候选被漏掉。复杂度是线性的：每个元素入栈一次、出栈至多一次，总操作不超过 2n 次。

把比较方向反过来，就得到「上一个更小」「右侧第一个更小」等变体——同批真题用它定「以某元素为最小值能覆盖的最远左右边界」，那道题的完整推导在真题复盘里，这里不重复展开。

单调队列的典型问题：滑动窗口最大值。

数组 1、3、-1、-3、5、3、6、7，窗口长度 k=3，要求每个窗口的最大值。规则两条：新元素入队前，把队尾所有比它小的下标删掉；每走一步，检查队首下标是否滑出窗口，滑出就删。删完入队，队首即当前窗口最大值。逐窗口结果是 3、3、5、5、6、7。

为什么队尾的小元素可以永久删除？新元素比它们大，下标又比它们新——旧元素滑出窗口时新元素还在窗口里，所以任何包含旧元素的窗口里都有个更大更新的存在，旧元素永远当不上最大值，留着只会挡路。线性复杂度的理由和单调栈一样：每个下标入队、出队各至多一次。

两种结构的代码实测。

用 Node.js 22 把两个模板跑出来，并各配一个暴力实现做对拍：

// 单调栈：下一个更大元素
function nextGreater(a) {
  const ans = new Array(a.length).fill(-1), st = [];
  for (let i = 0; i < a.length; i++) {
    while (st.length && a[st[st.length - 1]] < a[i]) ans[st.pop()] = a[i];
    st.push(i);
  }
  return ans;
}
// 单调队列：滑动窗口最大值
function windowMax(a, k) {
  const q = [], out = [];
  for (let i = 0; i < a.length; i++) {
    while (q.length && q[0] <= i - k) q.shift();
    while (q.length && a[q[q.length - 1]] <= a[i]) q.pop();
    q.push(i);
    if (i >= k - 1) out.push(a[q[0]]);
  }
  return out;
}
console.log(nextGreater([2, 1, 4, 3]));               // [ 4, 4, -1, -1 ]
console.log(windowMax([1, 3, -1, -3, 5, 3, 6, 7], 3)); // [ 3, 3, 5, 5, 6, 7 ]

输出与上面手工推演一致；再各跑两万组随机小规模用例与暴力解对拍，全部一致，模板才算可靠。

图 2：两种结构的不变量、弹出时机与适用问题对照。

怎么选：看问题问的是「边界」还是「窗口」。

题目里出现「下一个/上一个更大的元素」「最远能扩展到哪」「以某元素为最值的管辖范围」，选单调栈——它的本质是沿着单调性找每个元素两侧的边界，直方图最大矩形、接雨水都是这一族。题目里出现「每个长度为 k 的区间/窗口的最值」，选单调队列——它的本质是维护一个随窗口滑动而更新的最值候选集。两者都是 O(n)，分别把 O(n²) 的边界枚举和 O(nk) 的窗口扫描压到线性。

再往上一层：滑动窗口最值也能用堆做，但堆是 O(n log k)，而且懒删除写起来绕；单调队列是均摊 O(1) 的特化解。单调队列还能优化一类「窗口内取最值做转移」的动态规划，这是它超出模板题的价值。

学这类结构，建议的顺序是：先手工推一遍不变量为什么成立，再写模板，最后必须配暴力对拍——单调结构的错误大多藏在相等元素的取舍里。你第一次被单调结构惊艳到是哪道题？遇到窗口最值你会先想到堆还是双端队列？欢迎聊聊。