题解 | #接雨水问题#
接雨水问题
http://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f
思路：双指针
接水的多少取决于短板。因此指针left与right一左一右，每次取出最小值，从left往后寻找比最小值小的挡板，二者之差为当前挡板的接水量，直到遇到比它高的。同理，right也往中间寻找，直到遇到比它高的挡板。此时一轮大循环结束，重新计算left与right之间的最小值，开始新一轮的大循环。
public long maxWater (int[] arr) {
// write code here
int left=0;
int right=arr.length-1;
long water=0;
while(left<right){
//计算left与right挡板的较小值。
int min=arr[left]<arr[right]?arr[left]:arr[right];
while(left<right && arr[left]<=min){
water+=min-arr[left];
left++;
}
while(left<right && arr[right]<=min){
water+=min-arr[right];
right--;
}
}
return water;
}
