LeetCode#42接雨水

题目：
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例：

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

思路：

• 双指针，left right 同时遍历数组
• 想要接雨水，需要高度差，所以不断切换分左右两个方向来处理问题
• 能装多少雨水，取决于短板一侧，高度矮的一边
• 左边比右边矮的时候，从左向右出发，直到左边高于右边，然后从右向左出发，直到 left 和 right 走到中间位置
• 需要两个变量记录左侧和右侧的最高 leftMax，rightMax
• 在遍历过程中，如果新值大于之前的 Max 值，则更新 Max 值，如果小于 Max 值，说明有坑位可以接雨水，则结果加上 Max-当前值，左右只是方向不同，思路完全一样
• 当left和right碰在中间时，结束循环，返回结果

代码：

class Solution {
    public int trap(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int result = 0;
        while (left < right) { //左右在中间相碰时，退出循环
            if (height[left] < height[right]) { //从左向右接雨水
                if (height[left] > leftMax) {//值大更新
                    leftMax = height[left];
                } else { //值小累加雨水的值
                    result += leftMax - height[left];
                }
                left++; //向右移动
            } else {
                if (height[right] > rightMax) { //从右向左同理
                    rightMax = height[right];
                } else {
                    result += rightMax - height[right];
                }
                right--; //向左移动
            }
        }
        return result;
    }
}