数组——11. 盛最多水的容器

1 题目描述

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

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

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

说明：你不能倾斜容器。

2 题目示例

输入：[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

3 题目提示

n == height.length
2 <= n <= 105
0 <= height[i] <= 104

4 思路

矩阵的面积与两个因素有关：

矩阵的长度：两条垂直线的距离
矩阵的宽度：两条垂直线其中较短一条的长度
因此，要矩阵面积最大化，两条垂直线的距离越远越好，两条垂直线的最短长度也要越长越好。

我们设置两个指针 left 和 right，分别指向数组的最左端和最右端。此时，两条垂直线的距离是最远的，若要下一个矩阵面积比当前面积来得大，必须要把 height[left] 和 height[right] 中较短的垂直线往中间移动，看看是否可以找到更长的垂直线。

对于这种问题，不要想整体，而应该去想局部；本质就是动态规划思路，考虑如何处理没一个子问题即：位置 i，能装下多少水。

5 我的答案

 /** * 双指针解法 * 时间复杂度降 O(N)，空间复杂度 O(1) */
    public int maxArea(int[] height) {
    
        int size = height.length;
        int result = 0;
        int left_max = 0, right_max = 0;
        int left = 0, right = size - 1;

        while (left < right) {
    
            left_max = Math.max(left_max, height[left]);
            right_max = Math.max(right_max, height[right]);

            int currentArea = 0;
            //用 left 和 right 两个指针从两端向中心收缩，一边收缩一边计算 [left, right] 之间的矩形面积，取最大的面积值即是答案
            //矩形的高度是由 min(height[left], height[right]) 即较低的一边决定的：
            //移动较低的那一边，那条边可能会变高，使得矩形的高度变大，进而就「有可能」使得矩形的面积变大.
            if (left_max < right_max) {
    
                currentArea = left_max * (right - left);
                left++;
            } else {
    
                currentArea = right_max * (right - left);
                right--;
            }
            result = Math.max(result, currentArea);

        }

        return result;
    }