容器盛水问题
题目
分析
对于这个问题来说,最好的方法就是使用双指针(这也是官方推荐的,我看好多人也说这个方法时最快的);
如果使用双指针的话,就需要分析指针怎么移动:我们使用俩指针分别从头、尾开始标记,然后是用俩变量用来保存数据。然后用俩指针的边界来保证循环。每次开始保存一下俩边界的数据,然后对比俩边界哪边小,我们就处理那边。(这儿就是一个容器的原理,容器装水,肯定是最低的边决定的),然后开始再次循环,保证俩指针不越界并且当前的边值
不能大于我们当前情况下的最低边,把这个范围里面的装水,给加起来,并且将指针移动。直到最后指针相遇,我们就结束。
import java.util.*; public class Solution { /** * max water * @param arr int整型一维数组 the array * @return long长整型 */ public long maxWater (int[] arr) { // write code here long res=0; int left_Height, right_Height; int left=0, right = arr.length - 1; while (left < right) { left_Height = arr[left]; right_Height = arr[right]; if(left_Height < right_Height) { while(left < right && arr[left] <= left_Height) { res += left_Height - arr[left]; left++; } }else { while(left < right && arr[right] <= right_Height) { res += right_Height - arr[right]; right--; } } } return res; } }
新平台的第一次,快半年没有写了吧!以后加油!