LeetCode_05_ContainerWithMostWater

1. question：盛水最多的容器（中等）

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water

示例 1：

输入：[1,8,6,2,5,4,8,3,7]
输出：49 
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

2. answer

思路：

这道题仔细阅读之后，就会发现，实际上是比较某两个元素的计算结果，选择最大值。计算公式为：min(height[i], height[j]) * (j - i)。

最简单地先用暴力破解法做一下。

代码如下所示：

public class Solution_0005 {

    public static int maxArea(int[] height) {

        int result = 0;
        int h;
        for (int i = 0; i < height.length; i++) {
            for (int j = i + 1; j < height.length; j++) {
                h = Math.min(height[i], height[j]);
                result = Math.max(result, h * (j - i));
            }
        }
        return result;
    }
    public static void main(String[] args) {
//        int[] height = {1,8,6,2,5,4,8,3,7};
        int[] height = {1, 1};
        System.out.println(maxArea(height));
    }
}

暴力破解法就是双层循环，分别获取两个元素，然后计算结果，遍历数组，比较取得最大值。这样做的时间复杂度是O(n^2)，那么怎么做可以降低时间复杂度呢？

实际上，暴力法是将每个组合都比较了一遍，那么能不能将一些没用的组合（明显低于最大值）不比较呢？

首先从形象上说，暴力法中的两个元素实际上就是容器的两条边。遍历数组就是遍历移动两条边，使得容器的面积最大。

那么减少边的移动次数（减少组合次数），就相当于过滤了一些没用的组合，降低了时间复杂度。怎么减少移动次数呢？实际上就是如果移动之后的面积肯定小于或等于移动之前的面积，那么此次移动就是没用的，应该不移动。

面积由底×高组成，为了更加方便，可以控制底(j - i)在移动的时候是减少的，只需要保证高是增加的即可。

采用双指针法，两个指针初始位置在数组的头和尾，指针向内移动，保证了之后的移动过程中底是减少的。那么怎么保证高是增加的呢？即保证min(height[i], height[j])是增加的？

因为高是由最短的边（i或者j）决定的，所以只要最短的边是变化的就可以，即就有几率变大。（如果改变最长的边，最短的边只能不变或者更小，肯定不会增大）。总体上高就有可能变大，容器的面积就有可能变大。

参考精选题解。考虑一下双指针的做法：

•  首先两个指针在数组的两端，移动指针相当于移动水箱的两边。那么怎么移动才会减少不必要的比较呢？
  

•  首先，此时水箱的底边（y - x）的距离是最大的，那么无论怎么移动，底边它都会变小，现在要做的就是使得 高 变大。
  

•  而 面积 为 min(height[x], height[y]) * (y - x)
  

•  所以，必须 使得 min(height[x], height[y]) 可能增大，因为这样，最终结果才有可能变大
  

•  而 min(height[x], height[y]) 的值取决于较小的边，那么如果我们改变较大的边，此时较大的边要么增大，要么减小。
  

•  但是，即使再增大，较小的边没有变，所以min()值保持不变，仍然是较小的边；如果较大的边减小的话，就更不用说了，min()的值可能减小，也可能不变。  所以，改变较大的边，水箱面积保持不变或减小，肯定不会增大。（即包含了不必要的移动，所以这些移动是浪费的）
  

•  那么如果移动较小的边呢？也是有两种情况，该边要么增大，要么减小。如果该边增大的话，此时min()值肯定增大，如果减小的话，min()值肯定减小。  所以，改变较小的边，水箱面积有可能增大，也有可能减小。（既有不必要的移动，也有必要的移动）
  

•  所以，双指针应该移动较小的边。
  

代码如下所示：

public class Solution_0005_02 {

    public static int maxArea(int[] height) {

        int result = 0, temp = 0;
        int left = 0;
        int right = height.length - 1;

        while(left < right){

            temp = Math.min(height[left], height[right]) * (right - left);
            result = Math.max(result, temp);

            if(height[left] < height[right]){
                left ++;
            } else {
                right --;
            }

        }
        return result;
    }

    public static void main(String[] args) {
        int[] height = {1,8,6,2,5,4,8,3,7};
//        int[] height = {1, 1};
        System.out.println(maxArea(height));
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)。