5.4　单调栈与单调队列

学习目标：学完本节，你能

• 用单调栈解决"下一个更大元素"类问题；
• 用单调队列解决"滑动窗口最大值"类问题；
• 解释为什么嵌套了 while 却仍然是 $O(n)$；
• 说清这类算法真正的价值 —— 不是"总是更快"，而是"最坏情况有保障"。

先修：5.1（栈）、5.2（双端队列）、3.4（滑动窗口）。 固定术语：单调栈、单调队列。 环境与版本：.NET 8 / C# 12。 预计阅读：32 分钟。

一、直觉：排队时"比我矮的都出局"

想象一队人从左到右站好，每个人都在往右看，想找到第一个比自己高的人。

如果用一个栈来维护"还在等答案的人"，规则是这样的：

新来的人，会把栈里所有"比自己矮"的人都"解决掉" —— 因为他们等的就是这个人。

具体来说，新来的人身高 5：

• 栈里站着 3、1、4（从栈底到栈顶），他们都在等"比自己高的"
• 5 比 4 高 → 4 等到了，出栈，记下答案 5
• 5 比 1 高 → 1 等到了，出栈，答案 5
• 5 比 3 高 → 3 等到了，出栈，答案 5
• 栈空了，5 入栈，继续等

结果：栈里从栈底到栈顶，身高永远是递减的。 这就是"单调栈"。

为什么这个思路对？ 因为如果 5 比 4 高，那 4 右边第一个比它高的必定是 5（或更左边被挡住的）—— 更关键的是，4 后面的人再也看不到 4 了（5 挡在前面且更高），所以 4 可以"出局"了。

二、单调栈：下一个更大元素

问题：给一个数组，对每个元素找出它右边第一个比它大的元素。没有则返回 -1。

数组:  [3, 1, 4, 1, 5, 9, 2, 6]
答案:  [4, 4, 5, 5, 9, -1, 6, -1]
         ↑ 3 右边第一个比它大的是 4
                  ↑ 4 右边第一个比它大的是 5

暴力做法：对每个位置都往右扫一遍，$O(n^2)$。

单调栈做法：只扫一遍，$O(n)$。

static int[] NextGreaterStack(int[] a, ref long ops, bool trace = false)
{
    var result = new int[a.Length];
    Array.Fill(result, -1);
    var stack = new Stack<int>();               // 存下标，不是存值

    for (int i = 0; i < a.Length; i++)
    {
        ops++;
        // 当前元素比栈顶对应的值大 -> 栈顶元素找到答案了
        while (stack.Count > 0 && a[stack.Peek()] < a[i])
        {
            int idx = stack.Pop();
            result[idx] = a[i];
            if (trace) Console.WriteLine($"      a[{idx}]={a[idx]} 的答案 = {a[i]}（在 i={i} 处找到）");
        }
        stack.Push(i);

        if (trace)
            Console.WriteLine($"    i={i} (值 {a[i]}) 入栈 -> 栈内下标: [{string.Join(",", stack.Reverse())}]");
    }
    return result;
}

两个容易忽略的细节：

1. 栈里存的是下标，不是值。 因为最后要把答案写回 result[下标] —— 如果只存值，就不知道答案该写到哪。
2. while 里用 < 而不是 <=。 这决定了"相等"时算不算"更大"。本题要求"严格更大"，所以用 <。如果题目要"大于等于"，就改成 <=。

三、执行过程追踪

实测输出（数组 [3, 1, 4, 1, 5, 9, 2, 6]）：

  i=4 (值 5) 入栈 -> 栈内下标: [4]
      a[4]=5 的答案 = 9（在 i=5 处找到）
    i=5 (值 9) 入栈 -> 栈内下标: [5]
    i=6 (值 2) 入栈 -> 栈内下标: [5,6]
      a[6]=2 的答案 = 6（在 i=7 处找到）
    i=7 (值 6) 入栈 -> 栈内下标: [5,7]

  结果: [4, 4, 5, 5, 9, -1, 6, -1]

完整推演（前几步）：

看 $i=2$ 那一行：一个 4 进来，连续解决了两个人（1 和 3）。这就是"一次操作解决一批"的威力。

最终答案 [4, 4, 5, 5, 9, -1, 6, -1] 与暴力做法完全一致 ✓

四、为什么嵌套了 while 却还是 $O(n)$？

这是本节最需要理解的地方。代码里明明有嵌套循环：

for (int i = 0; i < a.Length; i++)        // 外层：n 次
{
    while (stack.Count > 0 && ...)        // 内层：看起来可能很多次
    {
        stack.Pop();
    }
    stack.Push(i);
}

关键在于：每个元素最多被 Push 一次，也最多被 Pop 一次。

• 入栈总次数 = $n$（每个下标恰好入栈一次）
• 出栈总次数 $\le$ 入栈总次数 = $n$（不能弹出比放进去更多的东西）

所以内层 while 在整个算法生命周期里，总共只执行了不超过 $n$ 次。

总操作数 $\le n$（入栈）$+ n$（出栈）$= 2n = O(n)$。

这和 3.4 节滑动窗口是同一个道理：left 指针只前进不后退，所以内层 while 的总执行次数有上界。均摊分析的又一次应用。

判断这类循环复杂度的通用方法：

问自己"内层循环的变量，总共能变多少次？"

• 如果内层操作会消耗某个"总量有限"的资源（栈的元素数、左指针的位置），那总量就是上界。
• 如果内层每次都能自由地跑满，那才是真正的 $O(n^2)$。

五、实测：一个必须看清的现象

这是本节最重要的一组数据。 我用两种不同的输入数组做对比：

  数据量都是 20,000，只换输入数据的分布：

  随机数组:
    暴力  : 比较        179,214 次 |     0.63 ms
    单调栈: 比较         20,000 次 |     2.28 ms
    结果一致 = True

  降序数组（最坏情况）:
    暴力  : 比较    199,990,000 次 |    37.63 ms
    单调栈: 比较         20,000 次 |     2.23 ms
    结果一致 = True

请仔细看第一组：随机数组下，暴力比单调栈还快（0.63 ms vs 2.28 ms）。

为什么？

因为随机数组里，"下一个更大元素"往往就在不远处。平均只需要往右看几步就能找到，暴力的内层循环很快就 break 了 —— 实测 20,000 个元素只比较了 179,214 次，平均每个元素只看 9 次。

它运气好。

但降序数组就完全不同了。 数组是 [20000, 19999, ..., 1]，每个元素右边都没有比它更大的，暴力必须一路扫到数组末尾才能确定。总比较次数：

$$\frac{n(n-1)}{2} = \frac{20000 \times 19999}{2} \approx 2 \times 10^8$$

实测 199,990,000 次，37.63 ms —— 慢 17 倍，而且这个倍数会随规模继续拉大。

而单调栈在两种输入下都是 20,000 次比较、2.2 ms 左右 —— 一步不多，一步不少。

所以单调栈的价值和 3.4 节的滑动窗口完全一样：

不是"总是更快"，而是"最坏情况有保障"。

你没法控制用户的输入数据长什么样。一个"最坏情况可预测"的算法，在生产环境里比"平均很快"的算法可靠得多。

这也解释了为什么在基准测试（benchmark）里，优化过的算法经常"输给"暴力解法 —— 因为测试数据往往是随机的，而随机数据恰恰是暴力解法运气最好的时候。

生产环境不是基准测试。 攻击者可以构造降序输入，用户可能上传一个完全排好序的文件。

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

问题：给一个数组和窗口大小 $k$，求每个窗口中的最大值。

数组: [1, 3, -1, -3, 5, 3, 6, 7]，k = 3
窗口:  [1  3  -1]                     最大值 3
          [3  -1  -3]                 最大值 3
              [-1  -3  5]             最大值 5
                   [-3  5  3]         最大值 5
                        [5  3  6]     最大值 6
                            [3  6  7] 最大值 7
结果: [3, 3, 5, 5, 6, 7]

暴力做法：每个窗口都重新遍历 $k$ 个元素找最大值，$O(n \cdot k)$。

单调队列做法：用一个双端队列维护"可能成为最大值的候选"，$O(n)$。

static int[] MaxWindowDeque(int[] a, int k, ref long ops)
{
    var result = new int[a.Length - k + 1];
    var deque = new LinkedList<int>();          // 存下标

    for (int i = 0; i < a.Length; i++)
    {
        ops++;
        // 1. 队首如果已经滑出窗口，踢掉
        while (deque.Count > 0 && deque.First!.Value <= i - k)
            deque.RemoveFirst();

        // 2. 队尾如果比当前值小，它永远不可能成为最大值了，踢掉
        while (deque.Count > 0 && a[deque.Last!.Value] <= a[i])
            deque.RemoveLast();

        deque.AddLast(i);

        // 3. 窗口形成后，队首就是当前窗口的最大值
        if (i >= k - 1)
            result[i - k + 1] = a[deque.First!.Value];
    }
    return result;
}

三步的分工：

第 ② 步是精髓。 想一想：如果队尾是 3，新来的是 5，那么：

• 3 比 5 小 → 只要 5 还在窗口里，3 就不可能成为最大值
• 3 比 5 老 → 5 出窗口一定比 3 晚

所以 3 永远没有出头之日了，直接扔掉。

这就是"单调队列"这个名字的由来：队列里存的下标对应的值，从队首到队尾严格递减。队首永远是最大值。

注意用的是双端队列（5.2 节）：队首踢元素（步骤 ①）和队尾踢元素（步骤 ②）都要 $O(1)$ —— 普通队列只能在一端操作，做不到。

为什么也是 $O(n)$？ 同样是均摊：每个下标最多入队一次、出队一次，所以两个 while 的总执行次数都不超过 $n$。

七、实测：滑动窗口最大值

  数组: [1, 3, -1, -3, 5, 3, 6, 7]，窗口大小 k=3
  暴力结果  : [3, 3, 5, 5, 6, 7]
  单调队列  : [3, 3, 5, 5, 6, 7]
  一致: True

           数据量 |     窗口 |           暴力比较次数 |         单调队列比较 |       倍数
      10,000 |    100 |          990,100 |         10,000 |      99 倍   一致=True
      10,000 |  1,000 |        9,001,000 |         10,000 |     900 倍   一致=True
      50,000 |    100 |        4,990,100 |         50,000 |     100 倍   一致=True
      50,000 |  1,000 |       49,001,000 |         50,000 |     980 倍   一致=True

  实际耗时（数据量 200,000，窗口 1000）：
    暴力    :    51.37 ms
    单调队列:     4.96 ms
    快 10 倍，结果一致 = True

这组数据比"下一个更大元素"那组更"干净"，因为：

滑动窗口最大值的暴力做法没有"提前退出"的运气。

每个窗口都必须看完全部 $k$ 个元素才能确定最大值 —— 没有任何捷径。所以暴力的代价是稳定的 $O(n \cdot k)$，不管你给什么数据。

这就带来两个观察：

1. 窗口越大，差距越大：$k$ 从 100 涨到 1000（10 倍），比较次数的倍数从 99 涨到 900（约 9 倍）。倍数正比于 $k$。
2. 数据量翻倍时，两者的倍数关系不变（10,000 和 50,000 的数据下，$k=1000$ 都是约 900 倍）。因为一个是 $O(nk)$，一个是 $O(n)$，比值就是 $k$。

对比一下两个问题的差别：

	下一个更大元素	滑动窗口最大值
暴力的复杂度	$O(n \times \text{平均距离})$	$O(n \times k)$
随机数据下	很快（距离短）	一样慢（必须看满 $k$ 个）
有什么保障	没有	没有
优化后	$O(n)$	$O(n)$

下一个更大元素的暴力"运气成分"很大，滑动窗口最大值的暴力则"稳定地慢"。 但这不影响结论：两个优化版本的共同价值都是"把不可预测变成可预测"。

八、什么时候该想到单调栈/单调队列？

识别口诀："找最近的那个比我大/小的" → 单调栈；"窗口内的最值" → 单调队列。

九、练习

练习 5.4.1（手写推演） 数组 [5, 2, 8, 1, 9, 3]，手工推演单调栈求"下一个更大元素"的全过程： 列出每一步的 i、a[i]、栈内下标、以及产生的答案。

练习 5.4.2（变体） 如果要找"下一个更小元素"（右边第一个比它小的），单调栈的代码要改哪一行？

练习 5.4.3（手写推演） 数组 [4, 2, 7, 1, 5]，窗口大小 $k = 3$，手工推演单调队列求每个窗口最大值的过程。 列出每一步队列的内容（存下标），并说明每一步为什么踢掉某些元素。

练习 5.4.4（判断） 判断对错并说明理由： (a) 单调栈一定比暴力快。 (b) 单调栈里的元素是单调递增的。 (c) 单调队列用普通队列（Queue<T>）实现也可以，只是代码麻烦一点。

练习 5.4.5（挑战·柱状图最大矩形） 给定一个非负整数数组，表示柱状图中每个柱子的高度（宽度都是 1），求其中能勾勒出的最大矩形面积。

输入: [2, 1, 5, 6, 2, 3]
输出: 10   （由高度 5 和 6 两根柱子组成 5×2 的矩形）

要求 $O(n)$。提示：对每根柱子，找出"以它为高的最大矩形"能延伸到多宽 —— 这等价于找"左边第一个比它矮的"和"右边第一个比它矮的"。

十、练习答案

5.4.1

数组 [5, 2, 8, 1, 9, 3]：

结果：[8, 8, 9, 9, -1, -1]

验证：

• 5 右边第一个更大的是 8 ✓
• 2 右边第一个更大的是 8 ✓
• 8 右边第一个更大的是 9 ✓
• 1 右边第一个更大的是 9 ✓
• 9 右边没有更大的 → -1 ✓
• 3 右边没有更大的 → -1 ✓

入栈/出栈总次数：入栈 6 次，出栈 4 次，共 10 次 = $2n - 2$ ✓ 不超过 $2n$

5.4.2

只要把内层 while 的比较符号反过来：

// 找「下一个更大」：当前元素比栈顶大时，栈顶找到答案
while (stack.Count > 0 && a[stack.Peek()] < a[i])

// 找「下一个更小」：当前元素比栈顶小时，栈顶找到答案
while (stack.Count > 0 && a[stack.Peek()] > a[i])

结果数组的初始化也从 -1 保持不变（找不到时返回 -1 是题目的约定，和方向无关）。

栈的单调性也随之改变：

• "下一个更大" → 栈内值递减（栈顶最小）
• "下一个更小" → 栈内值递增（栈顶最大）

记忆方法：栈顶的元素是"最容易被解决"的那个。 找更大时，最容易被解决的是最小的（来个稍大的就行），所以栈顶最小；找更小时反之。

5.4.3

数组 [4, 2, 7, 1, 5]，$k = 3$：

结果：[7, 7, 5]

验证：

• 窗口 [4,2,7] 最大值 7 ✓
• 窗口 [2,7,1] 最大值 7 ✓
• 窗口 [7,1,5] 最大值 5 ✓

每一步踢人的理由：

• $i=2$ 踢掉 1 和 0：7 比 2 大、比 4 大，而且 7 比它们更晚出窗口。2 和 4 永远没机会当最大值了。
• $i=4$ 踢掉 2：下标 2 对应的窗口范围已经过去了（$4-3=1$，下标 ≤1 的都滑出去了）。它已经不在窗口里。
• $i=4$ 踢掉 3：1 < 5，且 1 比 5 老。同第 2 条的理由。

注意 $i=4$ 时两个踢人动作的顺序：先踢队首（位置原因），再踢队尾（大小原因）。 顺序其实可以互换，但推荐按代码里的顺序（先位置、后大小），因为先清掉过期元素能让后面的判断更准确。

5.4.4

• (a) 错。 本节实测就是反例：随机数组下，暴力 0.63 ms，单调栈 2.28 ms，暴力更快。

  原因：随机数据里"下一个更大元素"就在附近，暴力几步就 break 了；而单调栈有 Stack 的方法调用开销。 单调栈保证的是最坏情况的 $O(n)$，不是"每次都更快"。

• (b) 错（说法不完整）。 要看找的是什么：
  • 找"下一个更大元素 → 栈内值递减（栈顶最小）
  • 找"下一个更小元素 → 栈内值递增（栈顶最大）

    笼统地说"单调栈是递增的"是不准确的，关键是"栈顶是最容易被解决的那个"。

• (c) 错。 单调队列必须用双端队列，因为：
  • 步骤 ① 要从队首删除（元素过期）
  • 步骤 ② 要从队尾删除（元素被淘汰）
  • 步骤 ③ 从队首读取

    普通 Queue<T> 只能"队首出、队尾进"，没法从队尾删除。所以必须用双端队列（LinkedList<T> 或自己实现的环形双端队列）。

    这是 5.2 节"双端队列"最典型的应用场景。

5.4.5

核心洞察：对每根柱子，以它为高的矩形，宽度受限于"左边第一个比它矮的"和"右边第一个比它矮的"。

高度: [2, 1, 5, 6, 2, 3]
下标:  0  1  2  3  4  5

以高度 5（下标 2）为例：

• 左边第一个比它矮的是下标 1（高度 1）
• 右边第一个比它矮的是下标 4（高度 2）
• 所以它只能在开区间 (1, 4) 内延伸 → 宽度 = $4 - 1 - 1 = 2$
• 面积 = $5 \times 2 = 10$ ✓

用单调栈一次性求出每个位置的"左边界"和"右边界"：

static int LargestRectangleArea(int[] heights)
{
    int n = heights.Length;
    var left = new int[n];       // left[i] = 左边第一个比 heights[i] 矮的下标
    var right = new int[n];      // right[i] = 右边第一个比 heights[i] 矮的下标

    // ---- 求左边界：从左往右扫，维护递增栈 ----
    var stack = new Stack<int>();
    for (int i = 0; i < n; i++)
    {
        while (stack.Count > 0 && heights[stack.Peek()] >= heights[i])
            stack.Pop();
        left[i] = stack.Count == 0 ? -1 : stack.Peek();   // 栈空表示左边没有更矮的
        stack.Push(i);
    }

    // ---- 求右边界：从右往左扫，逻辑对称 ----
    stack.Clear();
    for (int i = n - 1; i >= 0; i--)
    {
        while (stack.Count > 0 && heights[stack.Peek()] >= heights[i])
            stack.Pop();
        right[i] = stack.Count == 0 ? n : stack.Peek();   // 栈空表示右边没有更矮的
        stack.Push(i);
    }

    // ---- 算面积 ----
    int best = 0;
    for (int i = 0; i < n; i++)
    {
        int width = right[i] - left[i] - 1;
        best = Math.Max(best, heights[i] * width);
    }
    return best;
}

推演（[2, 1, 5, 6, 2, 3]）：

最大值 10 ✓

复杂度：两次扫描，每次都是单调栈的 $O(n)$，加上最后一遍 $O(n)$ —— 总共 $O(n)$。

注意 >= 而不是 >：当遇到等高柱子时用 >= 弹出，会让每根柱子只在一侧找到边界，避免重复计算同一个矩形。这个细节如果写错，答案仍然正确，但会做重复工作（也可能在某些变体里出错）。

这道题（LeetCode 84「柱状图中最大的矩形」）是单调栈的"毕业考题" —— 它需要你把几何问题转化成"找左右第一个更矮的"，这层转化才是难点，代码本身只是套模板。

这也说明了一件事：单调栈的代码很短，难的是识别出"这个问题可以转化成找最近的大/小元素"。

十一、常见错误

十二、本节总结

1. 单调栈维护一个内部单调的栈，用来找"下一个更大/更小元素"这类问题。栈里存下标。
2. 为什么是 $O(n)$：每个元素最多入栈一次、出栈一次，所以内层 while 的总执行次数不超过 $n$。
3. 单调栈不保证更快：实测随机数组下暴力 0.63 ms、单调栈 2.28 ms（暴力更快）；但降序数组下暴力 37.63 ms、单调栈 2.23 ms（快 17 倍）。
4. 它真正的价值是"最坏情况可预测" —— 你控制不了用户的输入分布。
5. 单调队列用双端队列维护窗口内的最大值候选，队首即最大值。三步：踢过期队首、踢更小的队尾、读队首。
6. 滑动窗口最大值的暴力没有"运气"（每个窗口必须看满 $k$ 个），所以实测倍数稳定在约 $k$ 倍（$k=1000$ 时差 900 倍）。
7. 这类算法的难点不在代码，在于"识别出问题可以转化" —— 柱状图最大矩形就是个例子。

本章小结：第 5 章讲完了两个最基础、也最常用的受限线性结构。

• 5.1 栈：后进先出。它的价值在于"接口足够窄"，所以实现简单、速度快、不易用错。别忘了 Pop 时清引用。
• 5.2 队列：先进先出。核心是环形缓冲区 —— 一个取模运算就把 $O(n)$ 变成了 $O(1)$。永远不要用 List.RemoveAt(0) 当出队。
• 5.3 应用：栈在表达式求值里的经典用法。调车场算法 + 后缀求值 = 一个完整的计算器。
• 5.4 单调栈/队列：栈和队列的进阶用法，把 $O(n^2)$ 降到 $O(n)$，而且给出了"最坏情况有保障"这个贯穿全书的主题的又一个例证。

下一章衔接：到这里，你已经学了数组、链表、栈、队列。它们都有一个共同的局限：要找一个元素，最坏情况都得把整个结构扫一遍（$O(n)$）。

有没有一种结构，能让"查找"接近 $O(1)$？

有。它叫哈希表，是 C# 里 Dictionary<TKey, TValue> 的底层结构。它是本书前半部分最重要的一个数据结构 —— 因为你每天都在用，却很可能没有真正理解它。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "5.4",
  "title": "单调栈与单调队列",
  "covered": [
    "单调栈的直觉（排队找第一个更高的人）",
    "下一个更大元素的实现（存下标而非存值）",
    "完整执行过程追踪与手工推演",
    "嵌套 while 仍为 O(n) 的均摊论证",
    "随机 vs 降序输入的对比（暴力反而更快 vs 慢 17 倍）",
    "单调队列的三步法（踢队首/踢队尾/读队首）",
    "滑动窗口最大值实测（k=1000 时差 900 倍）",
    "两个问题暴力解法的「运气」差异",
    "柱状图最大矩形（转化为找左右第一个更矮的）"
  ],
  "unresolved": [
    "柱状图最大矩形属于进阶应用，正文给出完整解法",
    "单调栈在 BFS 中的变体留到第 12 章"
  ],
  "canonical_terms": {
    "单调栈": "内部元素保持单调的栈，用于找下一个更大/更小元素",
    "单调队列": "内部元素保持单调的双端队列，用于求滑动窗口最值"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 5.1 的栈、5.2 的双端队列、3.4 的滑动窗口",
    "读者理解均摊分析的基本思路（3.2/3.4 已铺垫）"
  ],
  "word_count_actual": 3040,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch05/Sec54/",
    "实测数据逐项核对：随机 179214次/0.63ms vs 降序 199990000次/37.63ms；窗口最大值 900 倍",
    "暴力与单调实现的结果一致性已逐项校验（SequenceEqual=True）",
    "练习 5.4.1/5.4.3/5.4.5 的推演已手工验算",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "初版只测了随机数据，导致单调栈看起来比暴力还慢（2.01ms vs 1.41ms）且比较次数仅差 9 倍；已补降序数组（最坏情况）对照，并把「随机数据是暴力运气最好的时候」写成教学点"
  ],
  "next": "6.1 从数组下标到哈希函数"
}