LeetCode-11-盛水最多的容器

题目

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

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

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

说明：你不能倾斜容器。

示例 1：

img

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

提示：

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

题解

这一题的难点是双指针如何往里移动不会丢失最大值？

看了佬的方案，豁然开朗：

11. 盛最多水的容器 - 力扣（LeetCode）

首先是左右两指针l，r，两边高度分别为h[l]，h[r]，此时面积S(i, j) = min( h[l], h[r] ) * (r - l)

无论我们怎么移动两端的长板或短板，容器底边r - l均会-1；

如果向内移动短板，容器的短板min( h[l], h[r] )可能会减少，因此下一个容器的面积也可能会减小；

如果向内移动长板，容器的短板min( h[l], h[r] )不会减少，因此下个容器的面积一定会减小；

那么，我们每次移动长板就好了，更新面积的最大值，直到两板相遇，便可以得到最大面积。

class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1, res = 0;
        while(i < j) {
            // 移动长板
            res = height[i] < height[j] ? 
                Math.max(res, (j - i) * height[i++]):
                Math.max(res, (j - i) * height[j--]);
        }
        return res;
    }
}