储水量

问题

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

比如数组 [0,1,0,2,1,0,1,3,2,1,2,1]，在这种情况下，可以接6单位的雨水。

分析

1. 用两个变量分别表示当前元素左边最大值和右边最大值。

2. 用两个变量left ，right分别代表从左到右移动和从右到左移动的指针。

3. 如果当前元素的左边最大值比右边最大值小，则left指针向右移动，否则right指针向左移动。

4. 这种左右指针移动的目的是为了保证所求的左右最大值一定是当前元素的左右最大值。

参考：

https://blog.csdn.net/u013309870/article/details/70978279

解法

public static int water3(int []arr){
  int water=0;
  if(arr==null||arr.length<=1)
    return 0;
  int largestLeft=0,largestRight=0;
  //分别保存左右两边最大值
  int left=0,right=arr.length-1;
  while(left<right)
  {
    largestLeft=Math.max(arr[left], largestLeft);
    largestRight=Math.max(arr[right], largestRight);
    //获得左右两边最大值
    if(largestLeft>largestRight)
    {
      //如果左边最大值大于右边则右指针向移动
      water+=largestRight-arr[right--];
    }
    else {
      //否则左指针向右移动
      water+=largestLeft-arr[left++];
    }
  }

  return water;
}


//基于上面思想，自己写的
public static int chushui(int[] arr) {
        int sum = 0;
        int left = 0, right = arr.length - 1;
        int leftMax = arr[left], rightMax = arr[right];
        while (left < right) {
            if (leftMax > rightMax) {
                if (arr[right] <= rightMax)
                    sum += (rightMax - arr[right]);
                else
                    rightMax = arr[right];
                right--;
            } else {
                if (arr[left] <= leftMax) {
                    sum = sum + (leftMax - arr[left]);
                } else {
                    leftMax = arr[left];
                }
                left++;
            }
        }
        return sum;
    }