leecode算法-11盛最多水的容器
2022-03-06 18:06:45

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

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

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

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

说明：你不能倾斜容器。

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

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

开始解答：
解读题目的诉求，就是求最大的面积，可以理解程高度是 heign[n], 宽度为(n-i)数组之间距离的最大面积。这时我想到最简单的做法就是2层for循环去解决。示例如下：

public int maxArea(int[] height) {
    int max = 0;
    for (int i = 0; i < height.length; i++) {
        for (int j = 0; j < height.length; j++) {
            if (i == j) {
                continue;
            }
            int low = Math.min(height[i], height[j]);
            int width = j - i;
            max = Math.max(low * width, max);
        }
    }
    return max;
}

本地测试下，没有问题，准备提交，
结果是超出时间限制，看来还得想办法优化下。
重新回到题目，两次for循环是这样的，一个值固定不动，变另一个值，遍历所有的情况，执行的时间复杂度是 O(n²)，执行效率低，所以我们想办法把复杂度降低。
所以我们可以同时改边两个值，从height[0]和heignt[n-1]向内逼近。
即比较heignt[0]和heignt[n-1]向内移动，移动的规则为 那个值小，改变那个值。这样 就有了第二版代码，如下：

public int maxArea2(int[] height) {
    int max = 0;
    int i = 0;
    int j = height.length - 1;
    while (i < j) {
        int low = Math.min(height[i], height[j]);
        max = Math.max(low * (j - i), max);
        if (height[i] > height[j]) {
            j--;
        } else {
            i++;
        }
    }
    return max;
}

刚刚提到的那个值小移动那个就是这个

if (height[i] > height[j]) {
    j--;
} else {
    i++;
}

再次提交，顺利通过