在力扣 #11 问题里，我们可能会陷入这样的误区：装水的容器内部（即两侧的挡板之间）不能存在一个高于水平面的挡板。其实应该理解为，选中两块板，然后拆掉中间的所有板，求能放入由两者、$X$ 轴所限定区域的最大矩形面积。

这个面积的表示可以用数学符号来表示，下面我们将这个问题数学符号化。设每个挡板的高度为 $H_n$，其中 $0 \leqslant n \leqslant N-1$，$N$ 是挡板的数量。任意两块挡板，设序号为 $a$ 和 $b$ 且满足 $0 \leqslant a \leq b \leqslant N-1$，则由这两块挡板和 $X$ 轴限定的最大矩形面积可以表示为：

$$ area = (b-a) \times \min{\{H_a, H_b\}} $$

于是，问题转换为：设 $0 \leqslant a \lt b \leqslant N-1$ ，求 $area$ 最大值。

刚看到这个问题的时候，我们很难不考虑遍历所有的可能性。这个方法一定可以找出最终的结果，但是却显得非常不优雅且低效。假设我们从 $0$ 号挡板开始判断，那么每一个挡板都需要依次与编号比它大的所有挡板进行计算比较。所以可以用数学符号表示每一个挡板的比较次数 $C_n$ 为：

$$ \begin{aligned} C_0 =& N-1 \\ C_1 =& N-2 \\ \dots\\ C_{N-3} =& 2 \\ C_{N-2} =& 1 \end{aligned} $$

也就是：

$$ \begin{aligned} C &= \sum_{0}^{N-1} C_{n} \\ &= (N-1)+(N-2)+\dots+2+1 \\ &= \frac{N \times (N-1)}{2} \\ &= \mathrm{O}(N^2) \end{aligned} $$

即：把单次计算和比较看作一次原子操作，那么整个遍历过程的时间复杂度为 $\mathrm{O}(N^2)$。显然这样的方式不是我们想要的，我们需要思考一种复杂度更低的方式。

不妨考虑这样一种情况，如果我们已经知道最大值就在某个范围内，如何选择下一个值来进行比较？比如我们在某一次判断过程中，已知 $H_a \lt H_b$ 。那么下一步就要判断需要判定 $[a,b-1]$ 还是 $[a+1,b]$ 了。

$$ \begin{aligned} area &= (b-a) \times \min{\{H_a, H_{b}\}} \\ &= (b-a) \times H_a \end{aligned} $$

方案一，考虑 $[a,b-1]$，此时分两种情况：

情况 A，若 $H_{b-1} \leqslant H_b$： $$ \begin{aligned} area' &= (b-1-a) \times \min{\{H_a, H_{b-1}\}} \\ &\leqslant (b-1-a) \times \min{\{H_a, H_b\}} \\ &\lt (b-a) \times \min{\{H_a, H_{b}\}} \\ &= (b-a) \times H_a \end{aligned} $$

情况 B，若 $H_{b-1} \gt H_b$： $$ \begin{aligned} area' &= (b-1-a) \times \min{\{H_a, H_{b-1}\}} \\ &=(b-1-a) \times H_a \\ &\lt (b-a) \times H_a \end{aligned} $$

可见，从 $b$ 位置的挡板切换到 $b-1$ 时，一定有 $area' < area$。

方案二，考虑 $[a+1,b]$，此时分两种情况：

情况 A，若 $H_a \geqslant H_{a+1}$： $$ \begin{aligned} area' &= (b-a-1) \times \min{\{H_{a+1}, H_b\}} \\ &= (b-a-1) \times \min{\{H_a, H_b\}} \\ &\lt (b-a) \times H_a \end{aligned} $$

情况 B，若 $H_{a} \lt H_{a+1}$： $$ \begin{aligned} area' &= (b-a-1) \times \min{\{H_{a+1}, H_b\}} \end{aligned} $$

可见：

  • 从较短的一边 $a$ 位置的挡板切换到 $a+1$ 时，如果 $H_a \geqslant H_{a+1}$ ，则 $area' \lt area$ 一定成立；
  • 而 $H_a \lt H_{a+1}$ 时可能出现 $area' > area$ 的情况。

同理，若 $H_a \geqslant H_b$，上述结论仍然成立。

综上，如果已知最大值在范围 $[a,b]$，那么想要找到下一个潜在的更大的值，必须要将两端较短的一个向着另一边移动。在这个理论之下，我们可以摒弃很多无用的检查，可以一直重复上述移动过程直到最终两个端点挨到一起。这样一来，每一个高度值只会被判断一次，整体的时间复杂度就是 $\mathrm O(N)$。