TrappingRainWater

​ leetcode 42

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

image.png

​ 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）

​ 目标是取凹陷处的面积，第一想法，既然是凹陷处，那只要记录每个位置左边的最大高度和右边的最大高度，取这两者的最小值和本位置的高度比较，只要本位置的高度低于左右高度之中的最小值，即可计算凹陷处面积。
​ 所以创建两个数组存储每个点两边的最大高度。

        public int trap(int[] height) {
            int sum = 0;
            int[] left = new int[height.length];
            int[] right = new int[height.length];

            for (int i = 1; i < height.length - 1; i++) {
                left[i] = Math.max(left[i - 1], height[i - 1]);
            }
            for (int i = height.length - 2; i >= 0; i--) {
                right[i] = Math.max(right[i + 1], height[i + 1]);
            }
            for (int i = 1; i < height.length - 1; i++) {
                int min = Math.min(left[i], right[i]);
                if (min > height[i]) {
                    sum = sum + (min - height[i]);
                }
            }
            return sum;
        }

​ 而实际上取凹陷处的面积，只需要左右高度大于本位置高处即形成凹陷，只需要两个额外元素记录左右最大高度即可，也无需进行多次遍历，遍历一遍即可。代码如下

       public int trap(int[] height) {
           int left = 0;
           int right = height.length - 1;
           int ans = 0;
           int leftMax = 0;
           int rightMax = 0;
           while (left < right) {
               if (height[left] < height[right]) {
                   if (height[left] > leftMax) {
                       leftMax = height[left];
                   } else {
                       ans += leftMax - height[left];
                   }
                   left++;
               } else {
                   if (height[right] > rightMax) {
                       rightMax = height[right];
                   } else {
                       ans += rightMax - height[right];
                   }
                   right--;
               }
           }
           return ans;
       }

​ 初始化时，记录最左边的高度和最右边的高度为两边的最大高度。
​ 从左到右遍历，若本位置的高度大于边界值，则更新对应位置边界值；若本位置高度小于边界值，则计算本位置的面积加入总凹陷面积。