问题描述
给定一个整形数组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;
}
}
