本题的题目描述不太明确,需要一张示意图,在看别人的题解时看到这个图才明白是怎么回事。
所以本题的核心就是构造两边高而中间低的桶,这个桶能装的水取决于两边里面比较短的那一边。比如{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; }