【原】LeetCode第11题 盛最多水的容器

问题描述

来源：LeetCode第11题

难度：中等

给定一个长度为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^5

• 0 <= height[i] <= 10^4

视频分析

代码部分

1，以当前柱子为桶的高度，分别从两边查找

public int maxArea(int[] height) {
    int maxAre = 0;// 保存最大值
    int left = 0;
    int right = 0;
    int length = height.length;
    //以当前柱子为桶的左边界开始查找
    while (left < length) {
        // 从右边开始查找第一个不小于当前柱子的高度
        right = length - 1;
        while (left < right) {
            if (height[left] > height[right]) {
                right--;
            } else
                break;
        }

        //计算围成的面积
        int are = height[left] * (right - left);
        maxAre = Math.max(maxAre, are);
        left++;
    }

    right = length - 1;
    //以当前柱子为桶的右边界开始查找
    while (right > 0) {
        // 从左边开始查找第一个不小于当前柱子的高度
        left = 0;
        while (left < right) {
            if (height[right] > height[left]) {
                left++;
            } else
                break;
        }

        //计算围成的面积
        int are = height[right] * (right - left);
        maxAre = Math.max(maxAre, are);
        right--;
    }
    return maxAre;
}

2，双指针

public int maxArea(int[] height) {
    int maxAre = 0;// 保存最大值
    int left = 0;
    int right = height.length - 1;
    while (left < right) {
        maxAre = Math.max(maxAre, (right - left)
                * Math.min(height[left], height[right]));
        // 矮的柱子往中间靠
        if (height[left] < height[right])
            left++;
        else
            right--;
    }
    return maxAre;
}

3，双指针优化

public int maxArea(int[] height) {
    int maxAre = 0;// 保存最大值
    int left = 0;
    int right = height.length - 1;
    while (left < right) {
        int minHeight = Math.min(height[left], height[right]);
        maxAre = Math.max(maxAre, (right - left) * minHeight);
        // 如果两个柱子往中间靠的时候，有更短的或一样高的，直接跳过
        while (left < right && height[left] <= minHeight)
            left++;
        while (left < right && height[right] <= minHeight)
            right--;
    }
    return maxAre;
}

写了600多道算法题解了，都是文字版的，对于新手可能不是太容易理解。最近考虑录一些视频版的，我对录屏这方面没有经验，初期的视频可能比较啰嗦，大家就凑合着看吧，等我练熟了就好了。还可以关注我的B站账号：https://space.bilibili.com/439794202，我会把视频都放在上面，供大家免费观看