管辖区间与贡献法

1 · 管辖区间的定义

2 · 柱状图中的最大矩形

3 · 相等元素与重复计数

4 · 最大全 1 子矩阵

5 · 参考文献

贡献法 · largest rectangle

prevSmaller 与 nextSmaller 这一对答案有一种几何读法：对下标 $i$ ，若左边界是 $L$ 、右边界是 $R$ （都指向第一个比 $a[i]$ 小的位置），那么区间 $(L, R)$ 内的每一段包含 $i$ 的子数组，最小值都是 $a[i]$ 。这是 $i$ 的管辖区间，宽度 $R - L - 1$ ，它管辖的子数组条数是 $(i - L)(R - i)$ 。

一整类问题由这一步转写落地：柱状图中的最大矩形、01 矩阵中的最大全 1 子矩阵、所有子数组最小值之和。前两个求最大值，最后一个求总和，而这个差别决定了相等元素处的处理能不能马虎。

以 $h = [2, 1, 5, 6, 2, 3]$ 为例。取两侧边界都是严格更小的位置，越界按 next 记 6、prev 记 $-1$ ：

图 1-1 · 每个元素的管辖区间，浅蓝与深蓝两条短杠标出左右边界。可切换两侧边界的严格性，观察相等元素处区间如何伸缩。

最后一行的和是 21，恰好是长度 6 的数组的子数组总条数 $6 \times 7 / 2$ 。这一步在本例里碰巧成立：两个相等的 2 之间隔着更小的 1，谁也够不到谁。等值元素挨在一起时它就不再成立，那是 §3 的题目。

矩形的高只可能是某根柱子的高度：任取一个满足「内部每根柱子都不低于它」的矩形，把它往上顶到贴住最矮的那根柱子，面积不减。于是只需对每根柱子问一次「以它为高，最宽能到多少」，答案就是它的管辖宽度。

$h = [2, 1, 5, 6, 2, 3]$ 的六个候选面积是 2、6、10、6、8、3，最大值 10 出现在 $i = 2$ ，高 5、覆盖下标 2 到 3。

图 2-1 · 柱状图最大矩形。橙色是取到最大面积的那一段，下方逐柱列出管辖宽度与候选面积。可编辑柱高并单步观察栈的弹出顺序。

本节有一处与直觉相反的实测结果。求最大值时，两侧边界的严格性怎么配都得到同一个答案，尽管每根柱子拿到的宽度不同。全高为 4、长度 5 的柱状图上，两侧都严格给出的管辖条数是 $[5, 8, 9, 8, 5]$ ，左严右松给出的是 $[1, 2, 3, 4, 5]$ ，两者天差地别，但最大面积都是 20。

原因是「真正的最优矩形」总有某个代表能完整看到它：一段等高平台里，最左那根柱子在「左松右严」下拿到整段宽度，最右那根在「左严右松」下拿到整段宽度，而两侧都严格时两者都拿到。 $\max$ 对多算的候选免疫， $\sum$ 不免疫。测试里为这一条留了一组随机种子的断言：五组输入上宽度数组每次都不同，最大面积每次都相同。

子数组最小值之和要求每条子数组被数恰好一次。做法是给「谁是这条子数组的最小值代表」定一个唯一规则，边界的严格性就是这个规则的编码：

左边界取严格更小、右边界取小于等于：代表是平台里最右那个；
左边界取小于等于、右边界取严格更小：代表是平台里最左那个；
两侧都严格：平台里每个元素都认领整段，同一条子数组被数多次；
两侧都非严格：平台里每个元素都只认领自己，跨越平台的子数组无人认领。

$\sum_{\text{子数组}} \min = \sum_i a[i] \cdot (i - L_i)(R_i - i)$ ，其中 $L$ 与 $R$ 一个严格、一个非严格

误差的量级值得看清楚。长度 20 的全 1 数组，子数组共 210 条，答案就是 210。两侧都严格给出 1540，是正确值的 7.3 倍；两侧都非严格给出 20，只剩十分之一。含重复的随机数组上偏差小些但同样是系统性的：长度 30、值域 4 的三组种子，两侧都严格分别高出 47.5%、25.0%、13.9%，两侧都非严格分别低了 32.7%、22.2%、11.1%。

图 3-1 · 四种边界组合的贡献和与朴素枚举真值对照，两侧同严或同松的两列恒为错值。可调数组长度与值域，观察重复元素越多误差越大。

注 · 本节的两处口径都是被测试改过来的。

第一处是全等数组上「两侧都严格」的错值。原先按「每个下标都拿到整个数组」推出 $n^2$ ，写进测试后红了：实际是 $\sum_i (i+1)(n-i) = n(n+1)(n+2)/6$ ，长度 5 时是 35 而非 25，长度 20 时是 1540 而非 400。 $(i - L)(R - i)$ 在 $L = -1$ 、 $R = n$ 时是 $(i+1)(n-i)$ ，不是常数。

第二处是「代表取最左还是最右」。引擎里那个朴素计数实现按「并列最小取最左」写的，而注释写成了「对应左边界严格」，这两者正相反：左边界取严格更小意味着代表能向左跨过平台、不能向右跨，代表落在最右。逐项比对的测试立刻报了不等，注释随之改掉。

01 矩阵里的最大全 1 子矩阵是同一件事在二维的重复。逐行扫下来，为每一列维护「以本行为底、连续 1 的高度」，这一行的高度数组就是一个柱状图；对每一行跑一次最大矩形，取全局最大。行数 $m$ 、列数 $n$ 时总代价 $O(mn)$ 。

以四行五列的矩阵为例，逐行的高度数组依次是 $[1,0,1,0,0]$ 、 $[2,0,2,1,1]$ 、 $[3,1,3,2,2]$ 、 $[4,0,0,3,0]$ ，四行各自的最大矩形面积是 1、3、6、4，全局最大 6，落在第 1 行到第 2 行、第 2 列到第 4 列。

图 4-1 · 01 矩阵的最大全 1 子矩阵。上方是矩阵与命中的子矩阵，下方是当前行的高度直方图。可翻行、改矩阵密度，并对照朴素四重枚举的答案。

高度数组的一个性质让这套做法成立：某一行的高度只依赖上一行的高度与本行的 01 值（是 1 就加一，是 0 就归零），不需要回看更早的行。这也是它与「枚举上下左右四条边」的朴素解法的分野：后者要 $O(m^2 n^2)$ ，本系列的测试用它当外部真值，规模只敢开到 9 行 11 列。

宽度 $R-L-1$

面积 $h[i] \times$ 宽度

管辖条数 $(i-L)(R-i)$

Vandevoorde, D. (1998). The maximal rectangle problem. Dr. Dobb's Journal, 23(4). 柱状图最大矩形与全 1 子矩阵的栈解法及正确性论证。
Gabow, H. N., Bentley, J. L., & Tarjan, R. E. (1984). Scaling and related techniques for geometry problems. Proceedings of the 16th Annual ACM Symposium on Theory of Computing, 135–143. 区间最小值查询归约到 Cartesian tree 上的 LCA，管辖区间的另一种读法。
LeetCode 84 · Largest Rectangle in Histogram、85 · Maximal Rectangle、907 · Sum of Subarray Minimums。三道题分别对应本页 §2、§4 与 §3。