单调栈与单调队列

所以一个矩形只要说清两件事：从哪根到哪根（宽），这段里最矮的是多少（高）。 反过来也成立：每一个「最大矩形」，都可以说成「以某一根柱子的高度为高」的那一个 —— 因为最矮的那根就在里面，把高再抬一点点就会露出空隙。

★ 这句话是全章的入口：与其枚举「哪一段」，不如对每一根柱子问一句 「以我这个高度为高，最宽能铺到哪儿？」

⚠ 面积最大可到 2×10⁵ × 10⁹ = 2×10¹⁴，必须 long long。 这件事对拍永远查不出来（第 8 步有现场）。

8
2 1 5 0 3 5 5 6
       ↑        ★ 一根高 0 的柱子（题面允许），它把柱状图切成了互不相干的两段
             ↑↑ ★ 两根一样高的柱子（并列）
               ↑ ★ 结尾这一段是递增的 —— 记住这个特征，第 8 步有一个 bug 专门死在这儿

一根一根问「以我为高，能铺多宽」：

答案 15（第 6~8 根，高 5 宽 3）。

★ 请留意第 4 行那根 0 高柱：它能铺满整整 8 格，可高是 0，面积还是 0 —— 它唯一的作用是把左右两段隔开（左边最好的是 5，右边最好的是 15）。 ⚠ 顺带解释一件事：正解末尾要放一根「比谁都矮」的哨兵，写的是 −1 而不是 0 —— 因为题面允许 h = 0，写 −1 才严格比所有柱子矮，不用多想一步。

正解想的是「对每根柱子，左右第一个更矮的在哪」。 要是标准答案也这么想，两份代码就是同一个思路写了两遍 —— 只能验出打字错误，验不出想法错误 （第 9、15、34 章那条）。

所以这一份换个思路：每一段连续的柱子都试一遍，高取这段里最矮的。 mn 边扫边更新，所以是 O(n²) 而不是 O(n³)。

★ 更要紧的是：它两层循环里一次 break 都没有 —— n² 就老老实实是 n²。 下一步你会看到，这件事一点都不多余。

第 1 步那句话把题目变成了：

对每一根柱子，求出它左边第一个更矮的、右边第一个更矮的分别在哪。

单调栈就是干这个的。从左往右扫，栈里存下标，对应高度递增：

while (!st.empty() && h[st.back()] >= h[i]) {     // 新来的 i 比栈顶矮（或一样高）
    int t = st.back(); st.pop_back();
    int left = st.empty() ? 0 : st.back();        // ← 左边第一个比 h[t] 矮的
    ans = max(ans, h[t] * (i - left - 1));        // ← 右边第一个比 h[t] 矮的就是 i
    // 宽 = i − left − 1，那个 −1 是「两端那两根更矮的不算」
}
st.push_back(i);

★ 被弹出的那一刻，两个边界同时揭晓 —— 这是整个算法唯一需要理解的地方：

• 右边第一个更矮的，就是当前这个 i（它正因为更矮才把 t 挤出去）；
• 左边第一个更矮的，就是 t 被弹掉之后的新栈顶（因为栈里是递增的， 在 t 下面的那个一定比 t 矮；而中间那些更高的，早就被 t 自己弹掉了）。

★ 「栈里存的是下标不是高度」这件事，理由就在这一行：宽度要靠下标相减。

扫完之后栈里通常还剩一串（越往栈顶越高）—— 它们的右边界从来没揭晓过， 因为再没有更矮的柱子来把它们弹出去了。

在末尾放一根「比谁都矮」的哨兵（h = −1），主循环一个字都不用改， 它们就会被一口气全逼出来。默认那张图上，哨兵那一步一次弹掉了 4 根。

⚠ 忘了它，就是第 8 步那个 wrongTail.cpp。

for 里套着 while，凭什么说它是 O(n)？

错误的理由（很多人第一次是这么想的）：「每来一个新元素就弹一个，进出才平衡」—— 这个理由不但错，而且会让人把 while 写成 if（第 8 步那个 wrongOnce.cpp）。

正确的理由只有一句：

★ 每根柱子一辈子只入栈一次、只出栈一次。 所以那句 while 转的总圈数不会超过总出栈次数，也就是不超过 n —— 哪怕某一步一口气弹掉了 n−1 根，也不要紧，因为那 n−1 根再也不会回来了。

这就叫均摊：单看某一步可能很贵，但整趟下来总量是封顶的。 第 7 章双指针那句「两个指针都只往前走，所以是 O(n)」，说的是同一件事。

把柱状图换成单调递增、单调递减、全都一样高……入栈永远是 n+1、出栈永远是 n。 而 expand 那一行会从几十跳到几百亿（第 4 步那张表）。

★ 一个是「和数据无关的常数级工作量」，一个是「随数据形状剧烈变化」—— 这就是 O(n) 和 O(n²) 在计数器上的样子。

★ 四种形状差别巨大，三个计数器却只跟着 n 走。 这就是上一步那句话的画面版。 （这三个数都钉在 check:viz 里。）

⚠ 但请注意它们过程完全不同：单调不降时前面一根都弹不掉、全靠哨兵一次弹光； 单调不增时每来一根就弹一根。总量一样，节奏完全不一样 —— 均摊说的正是这件事。

点「运行 ▶」看结果

图 A 上它给 12（正解 15）。

w = i − t 相当于说「这根柱子只能从它自己站的地方往右铺」， 可它明明还能往左铺 —— 那些被它更早弹掉的、比它高的柱子，站的地方它当然也能站。

⚠ 它挑数据：如果最大矩形正好就是某一根柱子自己（宽 1），两种写法算出来一样。

点「运行 ▶」看结果

图 A 上它给 5 —— 正好是左半段的答案。

★ 因为图 A 结尾那一段（3 5 5 6）是递增的，它们全留在栈里没人结算， 而答案 15 恰恰就在那一段里。 ⚠ 所以这个 bug 只在「答案落在结尾那段递增上」时才现形 —— 生成器要是顺手让数据整体递减，它就永远 0 / 300。

点「运行 ▶」看结果

图 A 上它给 6（正解 15）。

★ 写成 if 的人，心里那个理由通常是「一次弹一个才平衡，这样才是 O(n)」—— 这个理由整个是反的（第 6 步）。而代价是：该弹的没弹干净， 栈从此不再单调，后面每一次「左边第一个更矮的」都可能读到一个比它更高的下标。

★ 把动画切到这一档，你会肉眼看见栈不再递增 —— 这个 bug 是能看出来的。

点「运行 ▶」看结果

图 A 上它给 48，离谱到一眼就能看出来（300 轮全被抓住）。

★ 方向由你要问的问题决定，不是背的： 这道题问「左右第一个更矮的」，所以栈里必须「越往上越高」； 要是问「第一个更高的」（比如「几天之后会有更暖和的一天」），方向就要整个反过来。

点「运行 ▶」看结果

while (h[st.back()] >= h[i])    // 遇到一样高的也弹
while (h[st.back()] >  h[i])    // 遇到一样高的不弹，留着

图 A 上两版结算出来的「高 × 宽」有 3 处不同（表里那三行 ★ 不）， 可最大值都是 15。300 组随机数据一组不差（钉在 check:viz 里）。

道理：一串等高的柱子里，>= 版让最右边那根算出完整的宽， > 版让最左边那根算出完整的宽 —— 两条路都保证那个完整的宽至少被算到一次， 而我们只要最大值。

⚠ 请和第 22 章对照：那一章 lower_bound 写成 upper_bound 是真 bug （300 组里 158 组答案不同），因为那道题问的是「严格上升还是非降」，等号就是题目本身。 ★ 同一个「一字之差」，一处致命一处无害 —— 差别在于你要的到底是什么。 （第 33 章「取决于数据的取值范围」、第 34 章「取决于题目问什么」之后的第三张脸。）

// ① 队尾：新来一个 a[i]，把队尾所有「不比它小」的弹掉
while (!q.empty() && a[q.back()] >= a[i]) q.pop_back();
q.push_back(i);
// ② 队头：如果队头那个下标已经滑出窗口，弹掉
if (q.front() <= i - k) q.pop_front();
// ③ 队头就是当前窗口的最小值
if (i >= k) cout << a[q.front()];

• 队尾那一句和单调栈一模一样：那些家伙又老又大， 只要 a[i] 还在窗口里，它们永远轮不到当最小值 —— 当场扔掉。
• 队头那一句是新的，它管的正是「窗口只有 k 宽」这件事。

★ 单调栈只从一头进出，单调队列两头都要动。多出来的那一头，就是「窗口」这两个字的全部代价。

★ 而这一头也顺便解释了为什么队列里必须存下标： 值用来比大小，下标用来判出没出窗口 —— 两件事，缺一不可。 （单调栈那道题存下标是为了算宽度，也是「值答不了的那半」。）

./winGenBig <k> 造的是 n = 200 000 的数据，只有 k 变（本机实测）：

★ 左边三列纹丝不动，右边那列涨了五千倍。这就是 O(n) 和 O(nk) 的全部差别。

播一遍就会发现，绿框有 3 格宽，可队列里常常只有 1~2 个 —— 没戏的早在进来的时候就被赶走了。

这正是「为什么它是 O(n) 而不是 O(nk)」的直观版： 我们从来没有把窗口里的 k 个数都留着。

点「运行 ▶」看结果

它给 -1 -3 -3 -3 -3 3（正解 -1 -3 -3 -3 3 3）。

光存值，「队头那个还在窗口里吗」这个问题就再也答不上来了， 只好拿队列长度冒充窗口宽度 —— 可队列里装的从来不是「窗口里的所有数」， 它通常比 k 短得多。于是该滑走的没滑走。

★ 要不要存下标，取决于你还要不要问「它是什么时候进来的」。

点「运行 ▶」看结果

它给 -1 -3 -3 -3 -3 -3。而它不是随机地错：

点「运行 ▶」看结果

一模一样。300 组随机数据一组不差（钉在 check:viz 里）。

★ 忘了弹队头 ≡ 前缀最值。 这是本教材第十一条这样的恒等式 （前十条在第 23、24、25、26、27、28、34 章）。 道理一句话：队头没人赶它走，而队尾那句 while 保证「比它更优的都进不来」—— 于是队头永远是从头到现在的最优值。 ⚠ 验法照旧：两份程序思路必须不同（一份用队列、一份一路 min 过去）。

点「运行 ▶」看结果

它给 -1 -3 -3 -3 -3 3 —— ⚠ 和上面那个「存值不存下标」的输出一模一样。

★ 第 28 章那条「两个不同的 bug，症状可以一模一样」的第二次。 而这一章还量出了更狠的：300 组数据里， 「忘了弹队头」和「出界差一格」同时对、同时错，一次例外都没有（各 182 / 300， 其中 58 组连输出都相同）。 一个方向能证明（差一格错了 ⇒ 队头是陈旧的 ⇒ 前缀最值也错）， 反过来只是实测没碰到反例 —— 这两句话的分量差得很远。 ⚠ 对拍只能告诉你「错了」，不能告诉你「错在哪」。 定位得靠 trace。

点「运行 ▶」看结果

它两行输出一模一样 —— 第一行（最小值）永远是对的，第二行永远是错的。

★ 这正好说明一件事：题面让你输出两整行，比让你输出一个数值钱得多。 如果这道题只要「所有窗口最小值之和」这么一个数，第二行那个 bug 根本没有出场机会。 （第 27、28 章「一份方案能自证清白，一个数字不能」的又一张脸。） ⚠ 第 12 步会量出这句话到底值多少 —— 那是这一章最刺眼的一张表。

多重背包的转移是（第 i 种物品，价值 v、重量 w、至多 k 件）：

f[j] = max over 0 ≤ t ≤ k  of  f[j − t·w] + t·v

★ 右边只用到 j, j−w, j−2w, … —— 下标模 w 同余的那一串，彼此谁也够不着谁。 于是把容量按 j mod w 分组。设 j = r + s·w，g[s] = f[r + s·w]：

g[s] = max over 0 ≤ t ≤ k  of  g[s − t] + t·v
     = max over s−k ≤ s' ≤ s of ( g[s'] − s'·v ) + s·v        ← 换元 s' = s − t

括号里那一坨只和 s’ 有关，s·v 提得出去 —— 于是它就是「在 g[s'] − s'·v 这个序列上求宽度 k+1 的滑动窗口最大值」， 正是这一章前半章那道题。每个容量只被处理一次 → O(nW)。

★ 那个「提出去的 s·v」还顺带把第 9 步那句话又说了一遍： 队列里比的是 g[s'] − s'·v（值），窗口边界是拿 s（下标）判的。

cd code/24-knapsack-multi && g++ -O2 -std=c++17 -o multiGen multiGen.cpp
for s in $(seq 1 300); do ./multiGen $s > t.txt
  diff <(../35-monotonic/multiQueue < t.txt) <(./multi < t.txt) || echo "seed $s 不一致"
done

300 组，一组不差（枚举每种拿几件的 multiBrute.cpp 也一起对了）。 这是本教材第二次跨章节交叉验证（第一次是第 30 章把第 13 章那张网格图转成图跑）。

gen.cpp 带了八个档位（./gen 种子 档位），种子固定 1..300：

★ 档位 3 那一行是这一章的定盘星：结尾递增这一处改动， 把「忘了哨兵」从 122 抬到 199，「只弹一根」从 164 抬到 246 —— 因为这个 bug 的现场只有一种：答案落在结尾那段没人结算的柱子上。

★ 档位 4 是一次撤回。 题面允许 h = 0，多造点 0 高柱看起来只会让覆盖更全， 实测却是三个 bug 一起掉（206→184、199→185、246→219）。 原因很实在：0 高柱把柱状图切成了几段短的，每段能攒的栈都变浅了， 而这一章的 bug 全都要靠「栈里攒着好几根」才现形。 ⚠ 而且 0 本来就有 —— 值域是 [0, 9]，档位 3 已经有 114 / 300 组带 0 了。

★ 「多加一点」和「数据变好了」是两件事（第 33 章那条的第二次； 第 34 章「调生成器要允许撤回」的第二次）。

• 台阶（档位 5）：撤了之后「宽度差一」掉 30 —— 有用，留。
• 结尾递增（档位 6）：撤了之后「忘了哨兵」掉到 122 —— 最有用的一处，留。
• ⚠ 值域压小（档位 7）：撤了之后几乎一个数都没变（甚至略好一点）。

★ 为什么值域压小没用了？因为**「台阶」那处改动把它想干的事包办了** —— 并列的高度是靠「抄上一根」造出来的，和值域宽窄没关系。

★ 第 32 章「调优不可加：一处改动值不值得留，取决于其它旋钮此刻在哪」的第三次。 两处改动想做同一件事时，后来的那处会把前面那处吃掉。

它最后还是留下了，但理由不是抓获率：值域 [0, 999] 时 300 组里只有 2 组带 0 高柱， 而 h = 0 是题面明确允许的边界（第 24 章那条：退化的那一端也必须造）。 这笔账明写在这里，不粉饰成「改了就是更好」（第 27 章档位 3 的同款）。

★ 档位 1 是「某一支占得太多」的第五次：k 取到 1 和 n 是两个退化端 （k = 1 时答案恒等于原数组，k = n 时只有一个窗口）—— 加上它们本身是对的（第 24 章那条）， 可一口气占到 180 / 300，四个 bug 全线腰斩。降到各八分之一之后回涨。 ⚠ 但要老实说：回涨之后（147/189/189/269）仍然不如什么都不加的档位 0（247/262/262/300）。 这两个退化端是拿抓获率换来的覆盖，我留下了它们，账写在这里。

★★ 档位 4 才是这一章最值得记的一格。 我本来断定「数据一单调，四个 bug 一起隐身」—— 因为窗口最小值永远待在最右边，滑不滑走都一样。只对了一半：

• 只看最小值那一行：四个 bug 全部 0 / 300，一个都测不出来 —— 直觉是对的；
• 可题面同时要最大值那一行，在那一行上它们全现形了（174 / 239 / 239 / 269）。

★ 同一个顺手写法，在同一道题的两问里效果正好相反。 这也解释了这道题为什么要一次问两个方向：多问一问，对拍就多一条腿。 （第 34 章那条「顺手写法危不危险，取决于题目在问什么」的加强版 —— 现在连「同一道题的两个问法」都能差出 0 和 239。）

【1】★★ 均摊分析：不是「内层转得少」，而是「每个元素一辈子只能出去一次」。 for 里套 while 照样可以是 O(n) —— 哪怕某一步一口气弹掉 n−1 个， 因为那 n−1 个再也不会回来了。 把这个理由记反了，就会把 while 写成 if（那才是真 bug）。 接的是第 7 章双指针那句「两个指针都只往前走」。

【2】★ 单调栈解的是「左右第一个更小 / 更大的在哪」，而不是「最值是多少」。 被弹出的那一刻，两个边界同时揭晓：右边界是当前这个 i，左边界是弹掉它之后的新栈顶。 ★ 所以栈里存的必须是下标 —— 宽度要靠下标相减。 方向（递增还是递减）由你要问的问题决定，不是背的。

【3】★ 单调队列 = 单调栈 + 多管一头。 队尾那句和单调栈一模一样；队头那句管的是「窗口只有 k 宽」。

★ 值用来比大小，下标用来判出没出窗口 —— 两件事，缺一不可。 忘了队头那一行，它就精确地变成了前缀最值（第十一条恒等式，300 组一组不差）。

【4】★ 多重背包的 O(nW)：把那个 max 写出来，它就是滑动窗口最大值。 按 j mod w 分组，换元把 s·v 提出去，剩下的正是本章前半章那道题。 ⚠ 但实测的交叉点在 k ≈ 100：k 小的时候二进制拆分更快（log k 才三四， 而单调队列常数重）。口诀要拿实测复核，这是第五次。

【5】★ 生成器的两次打脸，都在同一个地方：我以为的「关键的量」不是那个量。

• 「值域压小」在最终环境里几乎没用 —— 因为「造台阶」把它想干的事包办了 （调优不可加，后来的改动会吃掉前面的）；
• 「多造 0 高柱」看着更全面，实测三个 bug 一起掉（0 把柱状图切碎了，栈攒不起来）—— 撤回；
• 而「数据排成单调不增」只让最小值那一行全灭（0 / 300），最大值那一行照样抓 239。

★ 同一个顺手写法，在同一道题的两问里效果可以正好相反。