問題描述

給定一個整形數(shù)組arr，已知其中所有的值都是非負(fù)的，將這個數(shù)組看作一個柱子高度圖，計(jì)算按此排列的柱子，下雨之后能接多少雨水。(數(shù)組以外的區(qū)域高度視為0)

image.png

image.png

思路：采用雙指針
分別從兩邊往中間進(jìn)行計(jì)算，,當(dāng)左邊的高度小于右邊的高度時,左指針++,如果此時當(dāng)前位置的高度小于容器的左邊界高度,這個位置上方有水,進(jìn)行水量累加。
反之，則右指針向左掃描-1，如果此時當(dāng)前位置的高度小于容器的右邊界高度,這個位置上方有水,進(jìn)行水量累加

import java.util.*;


public class Solution {
    /**
     * max water
     * @param arr int整型一維數(shù)組 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;
            
    }
}