题解 | #接雨水问题#
接雨水问题
http://www.nowcoder.com/practice/31c1aed01b394f0b8b7734de0324e00f
双指针，先找到最高点，左边用双指针的时候只要关注更新left就可以了，因为右边有最高点，右边的话只要关注更新right就可以了
import java.util.*;
public class Solution {
/**
* max water
* @param arr int整型一维数组 the array
* @return long长整型
*/
public long maxWater (int[] arr) {
// write code here
long water=0;
int n=arr.length;
if(n==0){
return 0;
}
int maxIndex=0;
int maxValue=0;
for(int i=0;i<n;i++){
if(arr[i]>=maxValue){
maxValue=arr[i];
maxIndex=i;
}
}
int left=0;
int right=left+1;
while(right<maxIndex){
if(arr[left]>arr[right]){
water+=arr[left]-arr[right];
right++;
}
else {
left=right;
right=left+1;
}
}
right=n-1;
left=right-1;
while(left>maxIndex){
if(arr[right]>arr[left]){
water+=-arr[left]+arr[right];
left--;
}
else {
right=left;
left=right-1;
}
}
return water;
}
}
查看4道真题和解析
投递阿里巴巴等公司10个岗位
