基础数据结构

单调栈与单调队列

同一个念头的两种形态

单调栈和单调队列长得不像，解决的问题也不同：

  • 单调栈 —— 对每个元素，找它左边/右边第一个比它大/小的元素
  • 单调队列 —— 滑动窗口移动时，O(1) 拿到窗口内的最值

但它们是同一个念头的两种形态：

一个元素如果已经不可能成为任何一次查询的答案，就当场扔掉，永不回来。

扔掉的动作让每个元素最多进出容器各一次，于是那个看起来是嵌套的 while 被卡死在线性。剩下的全是细节：扔的判据是什么、从哪一端扔。

⭐ 这也是为什么它们必须建立在栈/队列上而不是数组上：只能从固定一端进出 这个限制，恰好就是「扔掉之后不会再回来」的保证。

单调栈：下一个更大元素

function nextGreaterElement(nums) {
  const res = new Array(nums.length).fill(-1);
  const stack = [];                 // 存下标，栈内对应的值单调递减

  for (let i = 0; i < nums.length; i++) {
    // 当前元素比栈顶大 → 它就是栈顶那些元素的「下一个更大」
    while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
      res[stack.pop()] = nums[i];
    }
    stack.push(i);
  }
  return res;                       // 栈里剩下的没有更大元素，保持 -1
}

[2,1,2,4,3] → [4,2,4,-1,-1]。最后两个都是 -1： 4 右边没有更大的，3 右边什么都没有。

📌 四个变体只改两处：

要找的 遍历方向 循环条件
右边第一个更大 从左往右 nums[top] < nums[i]
右边第一个更小 从左往右 nums[top] > nums[i]
左边第一个更大 从右往左 nums[top] < nums[i]
左边第一个更小 从右往左 nums[top] > nums[i]

🚨 栈里存下标，不要存值。 存值的话，res[...] 该写到哪一格就无从知道了 —— 而这个错在只要求「返回值列表」的题上碰巧不影响，换成「返回距离」的题 （比如每日温度）就立刻错。

存下标的写法里，i - j 就是距离：

while (st.length && T[st[st.length - 1]] < T[i]) {
  const j = st.pop();
  res[j] = i - j;                 // ⭐ 距离，只有存下标才算得出来
}

[73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]。

⚠️ 「把 O(n²) 优化成 O(n)」这句话，实测量不出来

单调栈几乎总是配着这句话出现。我拿它和暴力对照跑了一遍， 结果和这句话给人的印象差得很远（n = 20000，中位数）：

数据形状 单调栈 暴力 倍数 暴力内层平均步数
随机（值域 10⁹） 0.23ms 0.24ms 1.0x 9.15
递增 0.11ms 0.05ms 0.5x 1.00
递减 0.11ms 119.06ms 1050x 9999.50
全相同 0.13ms 86.48ms 643x 9999.50

随机数据上两者打平，递增数据上单调栈还慢一倍。

⭐ 最后那一列是与机器无关的量，其中三格有精确的闭式解： 递增是 (n-1)/n ≈ 1.00（右邻居就是答案，只有末元素一步都不走）； 递减和全相同都是 (n-1)/2 = 9999.5（内层永远找不到，走满整个后缀）。

原因就在这一列：暴力的内层循环找到第一个更大的就 break， 而随机数据下这一步平均只要走 ~9 步，根本走不满 n。

🚨 但「随机」这个词不够 —— 值域一小，结论就翻

同样 n = 20000，只改随机值的值域：

值域        暴力内层平均步数（11 个种子中位数）
0~9              1009.11   ← 比「打平」那一档大 110 倍
0~999               16.99
0~999999             9.15
0~10⁹                9.15

⚠️ 值域小 → 大量重复值 → 「严格更大」很难满足 → 内层一路扫下去。 用值域 0~9 的随机数据去测，单调栈会快出两个量级，「打平」这个结论直接翻转。 📌 所以上面那张表的第一行必须写成「随机（值域 10⁹）」。 「随机数据」从来不是一个口径，值域和长度都得说。

平均步数是对数增长的

值域取 10⁹（几乎无重复），11 个种子取中位数：

n 1000 5000 20000 80000 320000
实测平均步数 6.07 8.00 9.38 10.80 12.35
ln n 6.91 8.52 9.90 11.29 12.68
实测 / ln n 0.879 0.939 0.947 0.957 0.974

n 涨了 320 倍，平均步数只涨了 2.03 倍 —— 随机数据下暴力其实是 O(n log n)，不是 O(n²)。 ⭐ 而且「实测/ln n」这一列单调趋近 1，这比「两个数看着差不多」有力得多。 （更精确的理论值是调和数 H(n)：往右走 d 步还没遇到更大的，概率是 1/d， 求和就是 H(n) ≈ ln n + 0.577。实测一直略低于 H(n)，因为数组末尾的元素走不满。）

⭐ 所以单调栈真正的价值不是「平均快」，是消掉最坏情况： 递减数组上暴力退化到 1050 倍，而单调栈纹丝不动。 判题机的数据是照着卡最坏情况构造的，你面对的从来不是随机数据。

📌 这也是一条通用的读法：看到「把 O(n²) 优化成 O(n)」， 先问在什么数据上。很多优化只在特定形状的输入上兑现。

找边界：柱状图中最大的矩形

单调栈的第二类用法，比「下一个更大元素」难一档： 以每根柱子为高，能向左右扩到多宽？答案是两侧第一个比它矮的柱子之间。

难点在于左右边界要在同一次遍历里拿到。诀窍是看出栈那一刻：

function largestRectangle(h) {
  const a = [0, ...h, 0];           // ⭐ 两端哨兵，见下
  const st = [];
  let best = 0;

  for (let i = 0; i < a.length; i++) {
    while (st.length && a[st[st.length - 1]] > a[i]) {
      const height = a[st.pop()];
      // 出栈时：右边界就是 i，左边界是弹完之后的新栈顶
      const width = i - st[st.length - 1] - 1;
      best = Math.max(best, height * width);
    }
    st.push(i);
  }
  return best;
}

[2,1,5,6,2,3] → 10（高 5 和 6 那两根，宽 2）。

🚨 两端的哨兵 0 不是锦上添花，去掉之后有近一半的输入会错。

左端的 0 保证栈永远非空（st[st.length-1] 不会越界）， 右端的 0 保证遍历结束时栈被清空 —— 否则始终没被弹出的柱子从未参与计算。

🚨 而「去掉哨兵」有两种写法，症状完全不同（这一点必须先说清）：

写法 A  直接把 [0, ...h, 0] 改成 [...h]
        → 栈空时 st[st.length-1] 是 undefined，i - undefined - 1 = NaN
        → 结果是 NaN，官方样例都过不了，20000 组里 13125 组 NaN

写法 B  去掉哨兵、但给左边界加个兜底（st.length ? st[st.length-1] : -1）
        → 不会 NaN，安静地给一个偏小的数
        （实测与「只删右哨兵、保留左边那个 0」完全等价，50000 组零分歧）

下面这张表说的是写法 B —— 那个看起来更谨慎的写法：

输入 正确 写法 B（有兜底） 写法 A（无兜底）
[2,1,5,6,2,3] 10 10 ✅ NaN
[5,4,3,2,1] 9 9 ✅ NaN
[2,4] 4 0 ❌ 0
[1,2,3,4,5] 9 0 ❌ 0
[1,1,1] 3 0 ❌ 0
[6] 6 0 ❌ 0

⭐ 写法 B 全部偏小，一组偏大都没有 —— 漏算只会漏掉候选答案， 不会凭空造出更大的（换四种生成器 × 11 个种子，偏大的组数恒为 0）。

⚠️ 出错率取决于随机数组怎么生成，跨度不小：

生成器                出错率（11 个种子中位数）
长度1~20 值0~9              33.5%
长度1~10 值0~9              46.6%
长度1~10 值0~99             52.7%
长度3~30 值1~5              66.5%   ← 值域越窄、数组越长，越容易错

⚠️ 最值得注意的是前两行：力扣的官方样例 [2,1,5,6,2,3] 恰好是写法 B 能过的那一类， 递减数组也能过。错的是递增、全相同、单元素这些看起来更「简单」的输入。 📌 拿官方样例当自测用例，在这道题上会给你一个绿灯。

⭐ 顺带一个反直觉的对照：那个更粗心的写法（A）反而更安全 —— 它给 NaN，官方样例立刻就红。给你绿灯的是那个加了边界保护的谨慎写法。

接雨水：横着按层接

同一个模板换个结算方式。出栈的那根柱子是凹槽的底， 左右两侧是墙，接住的水量是「两墙较矮者减去底」乘以宽度：

function trap(h) {
  const st = [];
  let water = 0;
  for (let i = 0; i < h.length; i++) {
    while (st.length && h[st[st.length - 1]] < h[i]) {
      const bottom = h[st.pop()];
      if (!st.length) break;                    // 🚨 左边没墙，接不住
      const left = st[st.length - 1];
      water += (Math.min(h[left], h[i]) - bottom) * (i - left - 1);
    }
    st.push(i);
  }
  return water;
}

[0,1,0,2,1,0,1,3,2,1,2,1] → 6，[4,2,0,3,2,5] → 9。

⭐ 和柱状图那题的区别只在结算公式。弹出即结算这个骨架是一样的 —— 认出这一点，比记住两段代码有用。

单调队列：滑动窗口最大值

窗口滑动时要 O(1) 拿到窗口内的最大值。普通队列做不到，因为最大值可能在中间。 单调队列的办法是：只保留「还有可能成为最大值」的元素。

function maxSlidingWindow(nums, k) {
  const res = [];
  const dq = [];                    // 存下标，对应的值单调递减

  for (let i = 0; i < nums.length; i++) {
    // ① 队尾：比新元素小的都没机会了，弹掉
    while (dq.length > 0 && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
    dq.push(i);

    // ② 队头：滑出窗口了就弹掉
    if (dq[0] <= i - k) dq.shift();

    // ③ 窗口形成后，队头就是最大值
    if (i >= k - 1) res.push(nums[dq[0]]);
  }
  return res;
}

[1,3,-1,-3,5,3,6,7], k=3 → [3,3,5,5,6,7]。

⭐ 关键洞察在 ①：新元素进来时，队尾那些比它小的永远不可能再当最大值了 —— 因为它们比新元素早出窗口，又比它小。既然没机会，就没必要留。 这正是开头那句「不可能成为答案的，立刻扔掉」。

🚨 ② 的判断必须用下标比较（dq[0] <= i - k），不能用值。 队列里存下标而不是值，正是为了做这个判断 —— 和单调栈那条同源。

<= 还是 <：只在有重复值时才有区别

① 里两种写法结果都对（2000 组随机数据实测一致），差别在队列长度。 实测队列峰值长度（k = 100，n = 10000）：

（11 个种子取中位数，括号里是区间）

数据 <= <
全是同一个值 1 100
只有两种值 2 68 (64~70)
随机 0~9 8 (7~9) 25 (24~28)
随机 0~999999 13 (13~16) 13 (13~16)

⭐ 第一行的两个数是确定的、不用测：全相同时 <= 会把队尾全弹掉只留 1 个； < 一个都弹不掉，于是长度顶到窗口宽度 k = 100。

⚠️ 最后一行是重点：值域大到几乎没有重复时，两种写法完全一样 （中位数与区间逐格相同）。 < 的退化只发生在有大量重复值的数据上，而全相同的数组恰好是最坏情况 —— 队列长度退化到 k，空间从 O(1) 级别变成 O(k)。

📌 所以 <= 不是「更对」，是在最坏情况下更省。这类「平时看不出、 特定数据上才现形」的差别，正是判题机爱卡的地方。

单调队列 + 前缀和：和至少为 K 的最短子数组

滑动窗口有个隐含前提：元素全为正，窗口扩大时和单调增。 一旦有负数，这个前提就没了，滑动窗口会漏掉答案。

正确做法是把它转成前缀和上的问题：求最小的 i - j， 使 pre[i] - pre[j] >= k。然后用单调队列维护候选的 j：

function shortestSubarray(nums, k) {
  const n = nums.length;
  const pre = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) pre[i + 1] = pre[i] + nums[i];

  const dq = [];                    // 存下标，对应的前缀和单调递增
  let best = Infinity;
  for (let i = 0; i <= n; i++) {
    // ① 队头够得着 → 结算并弹出：它已经用过，且往后只会更长
    while (dq.length && pre[i] - pre[dq[0]] >= k) best = Math.min(best, i - dq.shift());
    // ② 队尾前缀和 >= 当前 → 它永远不如当前优（更长且起点更高）
    while (dq.length && pre[dq[dq.length - 1]] >= pre[i]) dq.pop();
    dq.push(i);
  }
  return best === Infinity ? -1 : best;
}

⭐ 这里两端都在扔，而且理由不同：队头是「已经结算完，留着只会更长」， 队尾是「被后来者全面压制」。单调栈只从一端扔，单调队列两端都扔 —— 这是两者唯一的结构性差异。

⚠️ 把它当普通滑动窗口写，症状是只在含负数时错：

（11 个种子 × 每种子 20000 组，报中位数）

数据 错的比例 换生成器后的跨度
全正数 0.0% 恒为 0.0%
含负数 19.4% 10.7% ~ 19.4%（数组越长越容易错）

📌 这个症状很坑：随手编几个全正数的例子自测，一次都不会错。 必须专门构造含负数的用例才能暴露它。比如 [84,-37,32,40,95], k=167 的答案是 3，滑动窗口给出 5。

🚨 更坑的是：力扣 #862 的三个官方样例，滑动窗口错版全部蒙对 —— 连含负数的那个也蒙对了：

A=[1]        K=1   答案 1    错版 1  ✅
A=[1,2]      K=4   答案 -1   错版 -1 ✅
A=[2,-1,2]   K=3   答案 3    错版 3  ✅   ← 含负数居然也过

⚠️ 所以「专门构造含负数的用例」还不够 —— 得构造那种「负数把前缀和拉回去、使更晚的起点反而更优」的用例。

怎么选

问题长什么样 用哪个
「对每个元素，找左/右第一个更大/更小的」 单调栈
「以每个元素为高/为底，能扩多宽」 单调栈（找边界）
「固定宽度的窗口滑过去，每个位置的最值」 单调队列
「变长窗口 + 有负数」 前缀和 + 单调队列

🚨 三条通用的坑，三个场景里都成立：

  1. 存下标，不存值 —— 要算距离、要判是否出窗口，都得靠下标
  2. 哨兵能省掉大半边界判断 —— 柱状图那题不加，三到七成的输入会错 （具体比例取决于数组怎么生成）
  3. 官方样例不是充分的自测用例 —— 上面 #84 和 #862 两处， 官方样例全部恰好能过（#862 连含负数的那个样例都被蒙对了）

⭐ 而真正要记的只有一句：不可能成为答案的，立刻扔掉。 四段代码的 while 循环，写的都是这一句话。

练习

勾选记录做过哪些，0 / 7 道。进度只存在这台设备的浏览器里；同一道题在别篇勾过，这里也会显示已做。

⚖️ 这里只给题号、官方标题和链接，不复述题面 —— 平台的题面文字有版权。 「这题考什么」写的是它对应本篇的哪个点，那部分是本站自己的内容。