11.盛最多水的容器

发表于 分类于 阅读次数：

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

说明：你不能倾斜容器。

示例 1：

示例图

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

示例 2：

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

示例 3：

1
2
输入：height = [4,3,2,1,4]
输出：16

示例 4：

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

解题思路

这是一道经典的双指针题目，也是面试中的高频考点。

核心思想

  • 使用双指针从两端向中间移动
  • 每次移动高度较小的指针
  • 记录过程中遇到的最大面积

为什么这样做是正确的？

  1. 面积计算：面积 = 宽度 × 高度 = (right - left) × min(height[left], height[right])
  2. 移动策略：总是移动高度较小的指针
  3. 正确性证明：移动高度较大的指针不会得到更大的面积

方法一：双指针解法（推荐）

时间复杂度 O(n)、空间复杂度 O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(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;
};

方法二：优化版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var maxArea = function(height) {
    let max = 0;
    let i = 0, j = height.length - 1;
    
    while (i < j) {
        // 计算面积并更新最大值
        max = Math.max(max, (j - i) * Math.min(height[i], height[j]));
        
        // 移动指针
        if (height[i] <= height[j]) {
            i++;
        } else {
            j--;
        }
    }
    
    return max;
};

方法三：暴力解法（不推荐）

时间复杂度 O(n²)、空间复杂度 O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
var maxArea = function(height) {
    let maxArea = 0;
    const n = height.length;
    
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const area = (j - i) * Math.min(height[i], height[j]);
            maxArea = Math.max(maxArea, area);
        }
    }
    
    return maxArea;
};

解题要点

  1. 双指针技巧：这是双指针的经典应用
  2. 移动策略：总是移动高度较小的指针
  3. 面积计算：面积 = 宽度 × 最小高度
  4. 优化思路：避免暴力枚举，使用双指针优化

面试要点

  • 高频考点：这道题是面试中的高频题目
  • 算法思维：考察双指针的应用
  • 时间复杂度：能够分析时间复杂度和空间复杂度
  • 代码简洁性：面试中要写出简洁清晰的代码

相关题目

扩展思考

  1. 为什么移动高度较小的指针是正确的？

    • 因为当前面积受限于较小的高度
    • 移动较大高度的指针不会增加面积

  2. 能否使用其他方法？

    • 暴力解法：O(n²) 时间复杂度
    • 分治法：可以但复杂度较高
    • 双指针是最优解法

  3. 边界情况处理

    • 数组长度为2的情况
    • 所有高度相等的情况
    • 高度为0的情况

最后更新: 2021-09-03