容器盛水问题

容器盛水问题

http://www.nowcoder.com/questionTerminal/31c1aed01b394f0b8b7734de0324e00f

本题的题目描述不太明确,需要一张示意图,在看别人的题解时看到这个图才明白是怎么回事。

图片说明
所以本题的核心就是构造两边高而中间低的桶,这个桶能装的水取决于两边里面比较短的那一边。比如{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;
  }

3 注意返回类型为 long

全部评论

相关推荐

点赞 评论 收藏
转发
12 收藏 评论
分享
牛客网
牛客企业服务