LeetCode-11-盛最多水的容器

11. 盛最多水的容器

给你 n 个非负整数 a1，a2，...，a``n，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 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

示例 3：

输入：height = [4,3,2,1,4]
输出：16

示例 4：

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

提示：

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

通过次数422,578

提交次数657,921

Container With Most Water

Medium

9187706Add to ListShare

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

Example 1:

img

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

Example 3:

Input: height = [4,3,2,1,4]
Output: 16

Example 4:

Input: height = [1,2,1]
Output: 2

Constraints:

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

算法流程： 设置双指针 i i,j j 分别位于容器壁两端，根据规则移动指针(左右两侧谁小就结算面积，向里面移动)，并且更新面积最大值 res，直到 i == j 时返回 res。

在一开始，我们考虑相距最远的两个柱子所能容纳水的面积，水的高度取决于两根柱子之间较短的那个即左边柱子的高度 h =1。水的面积就是1*8=8。

image-20210423094115738

第二步：如果固定左边的柱子，移动右边的柱子，那么水的高度一定不会增加，且宽度一定减少，所以水的面积一定减少。

image-20210423094511248

把(i,j)高度小的值的往里面挪动宽度虽然小了，但是高度变大，可以计算到新的大的water值

image-20210423094909365

class Solution {
    public int maxArea(int[] height) {
        if (height == null || height.length == 0) return 0;

        int l = 0, r = height.length - 1, water = 0;
        while (l < r) {
            if (height[l] <= height[r]) {
                int minH = height[l];
                water = Math.max(water, (r - l) * minH);
                while (l < r && height[l] <= minH) l++;
            } else {
                int minH = height[r];
                water = Math.max(water, (r - l) * minH);
                while (l < r && height[r] <= minH) r--;
            }
        }
        return water;

    }
}

image-20210423092336720