给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 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 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：
n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/trapping-rain-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一开始想用优先队列试试，结果到最后没想出来。
发现可以先找到一个最高的，之后从两遍向最高的遍历，用两个变量来维护两边相对更高的。
每次都添加一列的雨水。
0 1 2 3 4 5 6 7 8 9 10 11
如图：第一次遍历找到下标为7的柱子（最高的柱子）
然后从左边开始遍历，一开始指针为0，到下标为1的位置后，更新指针，到2的位置后，res = res + height[left] - height[i]。下标为3：更新指针；下标为4：加2 - 1 = 1，下标为5：加2 - 0 = 2；下标为2：加2 - 1 = 6,7的位置更新指针，然后左遍历结束。
从右边开始遍历，一开始指针为11，下标为10的位置，更新指针。下标为9：加 2 - 1 = 1；下标为8：更新指针；下标为7：更新指针。右遍历结束。
class Solution {
public int trap(int[] height) {
int maxIndex = 0;
for (int i = 0; i < height.length; i ++) {
maxIndex = height[i] > height[maxIndex] ? i : maxIndex;
}
int res = 0;
int left = 0;
for (int i = 0; i <= maxIndex; i ++) {
if (height[i] >= height[left]) {
left = i;
} else {
res += height[left] - height[i];
}
}
int len = height.length - 1;
int right = len;
for (int i = len; i >= maxIndex; i --) {
if (height[i] >= height[right]) {
right = i;
} else {
res += height[right] - height[i];
}
}
return res;
}
}
进行优化，利用双指针同时向中间遍历，每次移动高度较小的那个指针。
如果遇到某个位置比另一边更低，则说明该位置必定可以装到另一边的位置。
class Solution {
public int trap(int[] height) {
int ans = 0;
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
while (left < right) {
leftMax = Math.max(leftMax, height[left]);
rightMax = Math.max(rightMax, height[right]);
if (height[left] < height[right]) {
ans += leftMax - height[left];
left ++;
} else {
ans += rightMax - height[right];
right --;
}
}
return ans;
}
}
