大家好！我是曾续缘💜
今天是《LeetCode 热题 100》系列
发车第 5 天
双指针第 2 题
❤️点赞 👍 收藏 ⭐再看，养成习惯

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 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
提示：
n == height.length
2 <= n <= 10⁵
0 <= height[i] <= 10⁴
难度：💖💖

思路

容器盛水越大，肯定是盆越大越好，盆壁越高越好，对应本题就是两个柱子距离越远越好，柱高越高越好，根据木桶效应，再细化点就是两个柱子中较矮的柱子越高越好。

找到了影响答案的两个变量，如何进一步思考？每个柱高是题目给出的，无法事先得到什么规律，对于两柱距离，我们可以使其单调地变化，单调变大不好实现，因为不好确定初始位置，每边的柱子都是只能往一个方向走，不能走完所有可能。单调变小好实现，初始位置为数组的头和尾，相向移动，至少保证一边走完所有可能。

确定了一个两柱距离的变量后（初始位置为数组的头和尾），开始关注柱高（更细点是较矮的柱子的柱高），在保持一边柱子不动的情况下，我们肯定是贪心的移动较矮的柱子使两柱距离变小，因为如果移动高柱子，不管怎么移动高柱子，都确定地不可能使得矮柱子变高，也就不会使得盛水变多。移动矮柱子，虽然不确定能否使盛水量变多，但是有可能使其矮柱子变高，甚至高于目前的高柱子。看得出来，我们无法在移动的过程中知道当前的盛水量是否是最大值，在遍历结束后，取过程中的最大值作为答案。

解题方法

水量等于两个指针指向的数字中较小值 ∗ 指针之间的距离 开始时我们把两个指针指向数组的头和尾, 这时指针之间的距离是最大的, 把两个指针向中间移动的过程中, 可以知道指针之间的距离是不会变大而是变小的, 接下来就只需要考虑两个指针指向的数字中较小值了, 为了让较小值变得尽可能大, 我们移动较小值的指针. 在上面移动的过程中,会有多个可能的答案, 我们取最大值.

Code

查看代码

java

class Solution {
    public int maxArea(int[] height) {
        int ans = 0, l = 0, r = height.length - 1;
        while(l < r){
            int mn = Math.min(height[l], height[r]);
            int tmp = mn * (r - l);
            ans = Math.max(ans, tmp);
            if(mn == height[l]){
                l++;
            }else{
                r--;
            }
        }
        return ans;
    }
}

思路 ​

解题方法 ​

Code ​

思路

解题方法

Code