题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
解法
考虑任意位置$i$，它的雨水量取决于$i$两边的最大高度的最小值，即左边的最大高度 $L_{max}(i)$ 和右边的最大高度 $R_{max}(i)$ 中的较小值，设当前位置的高度为 $h(i)$，当前位置的雨水量为$f(i)$，有：
\[f(i) = min(L_{max}(i), R_{max}(i)) - h(i)\]那么总的接水量就是所有位置的雨水量之和$\sum_{i=1}^{n} f(i)$。
动态规划
我们想要知道每个位置的左边最大值和右边最大值，一个比较容易想到的方法就是分别从左到右和从右到左遍历一次，分别记录每个位置的左边最大值和右边最大值。
\[L_{max}(i) = max(L_{max}(i-1), h(i-1))\] \[R_{max}(i) = max(R_{max}(i+1), h(i+1))\]这需要至少两次遍历才能得到结果。先从左到右遍历一记录每个位置的$L_{max}$，再从右到左遍历一次记录每个位置的$R_{max}$,并同时计算每个位置的雨水量。
双指针
但这个题其实可以有一个巧妙的解法，只需要一次遍历就能得到结果。我们使用双指针从两边向中间遍历，设置两个指针为 $left$ 和 $right$，遍历的过程中维护两个变量 $l_{max}$ 和 $r_{max}$，分别代表$left$左边和$right$右边的最大值, 即：
\[l_{max} = L_{max}(left)\] \[r_{max} = R_{max}(right)\]根据公式 $f(i) = min(L_{max}(i), R_{max}(i)) - h(i)$，不失一般性，我们先考虑位置 $left$
\[f(left) = min(L_{max}(left), R_{max}(left)) - h(left)\]$L_{max}(left)$能够通过 $l_{max}$ 来维护，而 $R_{max}(left)$ 是未知的，但我们可以通过判断 $l_{max}$ 和 $r_{max}$ 的大小来间接的知道$R_{max}(left)$的范围。
如果 $l_{max} < r_{max}$，那么我们可以确定
\[L_{max}(left) = l_{max} < r_{max} \leq R_{max}(left)\] \[\Rightarrow L_{max}(left) \leq R_{max}(left)\] \[\Rightarrow f(left) = min(L_{max}(left), R_{max}(left)) - h(left) = l_{max} - h(left)\] \[\Rightarrow f(left) = l_{max} - h(left)\]同理，当 $l_{max} \geq r_{max}$ 时，$f(right) = r_{max} - h(right)$。
代码
int trap(vector<int>& h) {
int l = 0, r = h.size() - 1, l_max = 0, r_max = 0, ans = 0;
while (l < r) {
l_max = max(l_max, h[l]), r_max = max(r_max, h[r]);
ans += l_max < r_max ? l_max - h[l++] : r_max - h[r--];
}
return ans;
}