接雨水：不看整体，只看每根柱子
LeetCode 42：一排宽度为 1 的柱子，求下雨后能接多少水。这题真正的难点是建模。顺着直觉去找「有几个坑、每个坑装多少」，会发现坑的形状千变万化，程序很难写。换个角度——不分析整体，只分析局部：对每一个位置 i，求它头顶能积多高的水。
答案只取决于左右两边的「天花板」：
（若为负则是 0）。
于是问题变成：怎么求每个位置左右两侧的最大值？下面三种解法层层递进。
1 · 解法三：双指针 — O(1) 空间，边走边算
另外两种解法（见本页下方）都要先把所有位置的左右最大值存下来（
空间）。双指针的优势在于不必把两边最大值都精确求出。left 从左、right 从右对撞，维护 leftMax / rightMax。关键性质：若 leftMax < rightMax，那么 left 这一列的水位就由 leftMax 唯一确定——右边是否还有更高的柱子已不影响结果，因为「短板」已经确定在左边。于是结算 left、指针内移；反之结算 right。
为什么 leftMax < rightMax 时不用管右边到底多高？因为 left 位置的水位 =
。此刻 leftMax 已是 left 左侧（含自己）的真实最高；而右侧真实最高 ≥ rightMax > leftMax，所以 min 必定取 leftMax。信息已经够了，根本不必把右边走完。这就是双指针把
空间压成
的关键。
2 · 对照：另外两种解法
解法一 · 动态规划：正着、倒着各扫一遍，把每个位置的左/右最大值预存进数组，再逐位求和。直观，但要 额外空间。
解法二 · 单调栈：要确定一个坑能装水，得知道「后面出现了更高的柱子」——凡是需要回退的场景，栈都是好选择。维护一个高度递减的单调栈，遇到比栈顶高的柱子就弹栈、按「左墙、底、右墙」一层层横向结算积水。
三者殊途同归。DP 用空间换清晰、栈擅长「需要回退」的结构、双指针最省空间。对暴力解法的思考是优化的基础——这题难就难在连暴力枚举都不好想；一旦把视角从「整体的坑」切到「每根柱子头顶的水」，三条路就都通了。双指针的第三个流派——靠速度差工作的快慢指针——则主要服务于链表结构。