LeetCode_双指针_中等_11.盛最多水的容器-蒲公英云

LeetCode_双指针_中等_11.盛最多水的容器

1.题目

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画n条垂直线，垂直线i的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。

示例 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

示例 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

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

2.思路

（1）暴力穷举法
暴力穷举法应该是最容易想到的方法，其思想是使用两层 for 循环，遍历数组中的每一个数 x，然后计算其后面每一个元素与它构成容器后能够容纳的水量，并且用 res 来保存这个过程中的最大值，当循环结束后，res 的值即为所求。由于时间复杂度较高，所以在 LeetCode 上使用该方法提交会显示超出时间限制。

（2）双指针法

在最开始时，左右指针 left 和 right 分别指向数组的最左端和最右端，然后初始化水容量 res = 0，并且计算出此时的水容量 currentArea ，然后更新 res，即 res 取当前水容量与 res 之间的最大值；
又水容量是由指针之间的距离和两个指针指向的数字中较小值共同决定，故每次移动数字较小的那个指针；
两个指针相遇时，结束循环，此时的 res 的值即为容器可以容纳最多的水的值。

相关题目：
LeetCode_双指针_困难_42.接雨水

3.代码实现（Java）

//思路1————暴力穷举法
class Solution {
    public int maxArea(int[] height) {
        int length = height.lengt;
        int res = 0, h = 0;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                //容器的高度 h 取决于 height[i] 和 height[j] 中的最小值
                h = height[i] < height[j] ? height[i] : height[j];
                //(j - i) * h:计算容器能够容纳的水
                res = Math.max(res, (j - i) * h);
            }
        }
        return res;
    }
}
//思路2————双指针法
class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int res = 0;
        while (left < right) {
            // currentArea 为 [left, right] 之间的矩形面积
            int currentArea = Math.min(height[left], height[right]) * (right - left);
            //更新 res
            res = Math.max(currentArea, res);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return res;
    }
}