问题描述

给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)

image.png

image.png

思路：采用双指针
分别从两边往中间进行计算，,当左边的高度小于右边的高度时,左指针++,如果此时当前位置的高度小于容器的左边界高度,这个位置上方有水,进行水量累加。
反之，则右指针向左扫描-1，如果此时当前位置的高度小于容器的右边界高度,这个位置上方有水,进行水量累加

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一维数组 the array
     * @return long长整型
     */
    public long maxWater (int[] arr) {
        // write code here
        if(arr.length == 0){
            return 0;
        }
        int maxL = 0;
        int maxR = 0;
        int l = 0;
        int r = arr.length - 1;
        long area = 0;
        while(l<r){
          maxL = Math.max(maxL,arr[l]);
          maxR = Math.max(maxR,arr[r]);
          if(maxL<maxR){
             
              area += maxL - arr[l];
              l++;
             
          }else{
              area += maxR - arr[r];
              r--;
          }
        }
        return area;
            
    }
}