本题的题目描述不太明确,需要一张示意图,在看别人的题解时看到这个图才明白是怎么回事。
所以本题的核心就是构造两边高而中间低的桶,这个桶能装的水取决于两边里面比较短的那一边。比如{3,1,2} 这个数组能装的水等于
1 求得两边的最小值 2
2 用短的边减去中间波谷的值1得到结果1
则数组{3,1,2} 这些元素构成的容器最多能装1的水。
上面是题目解读,现在开始分析,本题考察的数据结构是数组,然后考察的算法是双指针,为什么是双指针尼?从前面的分析我们意识到我们的目标是要找到边界,要定义清楚左右,然后才能做累计和。而双指针的作用就是定位左右边界,双指针的核心就是什么时候移动指针?指针从什么地方开始为起点?。
一般双指针的指法有扩散法,夹逼法,还有就是类似滑动窗口的平移法。滑动窗口这个比较好理解就是首先有个指针往前走,走到给定的条件停下来,然后操作之后,再看看左右指针怎么个移法。
1 滑动窗口法 (未通过)
构造一个窗口,主要是指定各种边界条件的判断以及移动,比较复杂,要根据场景判断是否需要左右指针一起移动。
public long maxWater (int[] arr) {
// write code here
if(arr==null || arr.length==0){
return 0;
}
int left =0;
int right =0;
long res=0L;
while(left<=right && left<arr.length && right+1<arr.length){
if(left==right){
if(arr[right]>arr[right+1]){
right++;
}else{
left++;
right++;
}
}else{
if(arr[right]<=arr[right+1]){
right++;
}else{
res+=isCanPourWater(arr,left,right);
left=right;
}
}
}
res+=isCanPourWater(arr,left,right);
return res;
}
public long isCanPourWater(int [] arr,int left,int right){
long res=0L;
if(right-left>1){
int miner=arr[left]>arr[right]?arr[right]:arr[left];
for(int i=left+1;i<right;i++){
if(arr[i]>miner){
break;
}else{
res+=miner-arr[i];
}
}
}
return res;
}
2 夹逼法(通过)
每一次移动只看一边就好了,这种方法比较清晰
public long maxWater (int[] arr) {
// write code here
if(arr==null || arr.length==0){
return 0;
}
int left =0;
int right=arr.length-1;
long res=0L;
while(left<right){
int miner=arr[left]>arr[right]?arr[right]:arr[left];
while(left<right && arr[left]<=miner){
res+=miner-arr[left];
left++;
}
while(left<right && arr[right]<=miner){
res+=miner-arr[right];
right--;
}
}
return res;
}
京公网安备 11010502036488号