11 盛最多水的容器

一、题目

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

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

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

说明：你不能倾斜容器。

二、题解

思路：双指针 + 贪心

  1. 初始化：左指针 left 指向最左端，右指针 right 指向最右端，从最宽的底座开始。
  2. 木桶效应：容器的水量由较短的那根木板决定，面积 = min(height[left], height[right]) * (right - left)，每次更新最大值。
  3. 移动短板：每次移动较短的那根木板向中间靠拢。因为宽度必然减小，若移动长板，高度上限仍受短板限制，面积只会变小；只有移动短板才有机会遇到更高的板，从而让面积变大。
  4. 当 left 与 right 相遇时结束。
class Solution {
    public int maxArea(int[] height) {
        // 【初始化双指针】left 站在最左边，right 站在最右边。
        // 为什么要一开始拉到最宽？因为宽度是面积的决定性因素之一，先保证底座最宽。
        int left = 0, right = height.length - 1, maxArea = 0;

        // 只要左右指针没撞上，就不断计算和往中间挤
        while(left < right) {

            // 【计算当前面积】木桶效应：水的高度取决于“较短”的那根木板。
            // 面积 = 较短的木板高度 * 两根木板之间的距离 (right - left)
            int area = height[left] < height[right] ?
                       height[left] * (right - left) :
                       height[right] * (right - left);

            // 刷新历史最大面积记录
            maxArea = maxArea > area ? maxArea : area;

            // 【核心贪心逻辑：谁短谁往里走】
            // 如果移动高的那根木板，宽度一定减小，而水的高度最多只能跟原来短的一样，所以面积一定变小！
            // 只有把短的那根木板往里挪，才有可能遇到一根更高的木板，从而“逆风翻盘”让面积变大。
            if (height[left] < height[right]) {
                left++;  // 左边板子短，舍弃它，左指针往右找
            } else {
                right--; // 右边板子短，舍弃它，右指针往左找
            }
        }

        return maxArea;
    }
}

时间复杂度：O(n)O(n)

空间复杂度：O(1)O(1)

评论