011-盛最多水的容器 (Container With Most Water)

题目描述

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

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

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

说明： 你不能倾斜容器。

示例

输入：[1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

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

解题思路

使用双指针法，一个指针指向数组开头，另一个指向数组末尾。计算当前两个指针构成的容器面积，然后移动高度较小的指针向内移动，因为只有移动较小的指针才有可能获得更大的面积。

JavaScript 解决方案

/**
 * @param {number[]} height
 * @return {number}
 */
const maxArea = (height) => {
    let left = 0;
    let right = height.length - 1;
    let maxArea = 0;
    
    while (left < right) {
        // 计算当前容器的面积
        const width = right - left;
        const h = Math.min(height[left], height[right]);
        const area = width * h;
        
        // 更新最大面积
        maxArea = Math.max(maxArea, area);
        
        // 移动高度较小的指针
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxArea;
};

复杂度分析

时间复杂度：O(n)，其中 n 是数组长度
空间复杂度：O(1)，只使用了常数额外空间

测试用例

// 测试函数
const testMaxArea = () => {
    const testCases = [
        {
            height: [1, 8, 6, 2, 5, 4, 8, 3, 7],
            expected: 49
        },
        {
            height: [1, 1],
            expected: 1
        },
        {
            height: [4, 3, 2, 1, 4],
            expected: 16
        },
        {
            height: [1, 2, 1],
            expected: 2
        },
        {
            height: [1, 2, 4, 3],
            expected: 4
        },
        {
            height: [2, 3, 4, 5, 18, 17, 6],
            expected: 17
        },
        {
            height: [1, 3, 2, 5, 25, 24, 5],
            expected: 24
        }
    ];

    testCases.forEach((testCase, index) => {
        const result = maxArea(testCase.height);
        const passed = result === testCase.expected;
        console.log(`测试用例 ${index + 1}: ${passed ? '通过' : '失败'}`);
        console.log(`输入: height = [${testCase.height}]`);
        console.log(`期望: ${testCase.expected}, 实际: ${result}\n`);
    });
};

// 运行测试
testMaxArea();

关键点总结

双指针法：使用左右指针从两端向中间移动
面积计算：面积 = 宽度 × 最小高度
移动策略：移动高度较小的指针
贪心思想：每次移动都试图获得更大的面积
边界处理：指针相遇时结束循环

总结

这道题考察了以下重点：

双指针技巧：理解双指针在数组问题中的应用
贪心算法：通过局部最优选择达到全局最优
面积计算：理解容器面积的计算方法
算法优化：如何通过移动策略优化搜索

双指针法是最优解，时间复杂度为 O(n)，空间复杂度为 O(1)。在实际面试中，建议先解释双指针的思路，然后实现算法。

011-盛最多水的容器 (Container With Most Water)

On this page