盛最多水的容器

题目

盛最多水的容器

信息

• 类型：问答
• 难度：⭐⭐

考点

双指针,贪心算法,数组遍历

快速回答

使用双指针从数组两端向中间移动的贪心策略：

• 初始化左指针 left=0，右指针 right=height.length-1
• 计算当前容量：min(height[left], height[right]) * (right - left)
• 移动较小高度的指针（因为容量受限于较小高度）
• 更新最大容量并重复直到指针相遇
• 时间复杂度：O(n)，空间复杂度：O(1)

问题描述

给定一个非负整数数组 height，每个元素代表垂直线的长度。找出两条线与 x 轴共同构成的容器可以容纳最多的水。

原理说明

双指针法的核心思想：容量 = 宽度 × 最小高度。从最大宽度开始（数组两端）：

1. 初始状态：左指针在索引0，右指针在末尾，此时宽度最大
2. 关键洞察：移动较小高度的指针（因为容量受限于较小高度，移动较大高度的指针不可能增加容量）
3. 贪心策略：每次移动都尝试寻找更高的边界，从而可能获得更大容量

代码示例

def maxArea(height):
    left, right = 0, len(height) - 1
    max_water = 0

    while left < right:
        # 计算当前容量
        h = min(height[left], height[right])
        w = right - left
        max_water = max(max_water, h * w)

        # 移动较小高度的指针
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water

最佳实践

• 指针移动条件：始终移动高度较小的指针，因为这是提升容量的唯一可能
• 提前终止：当 width * max_possible_height ≤ current_max 时可提前终止（需预计算最大高度）
• 边界处理：空数组或单元素数组直接返回0

常见错误

• 错误移动指针：同时移动两个指针会错过潜在解
• 暴力解法：使用双重循环（O(n²)）会导致超时
• 高度误解：误认为移动指针时高度会线性增加，实际取决于具体值

扩展知识

• 贪心证明：每次移动较小高度指针相当于排除了不可能成为最优解的状态
• 变种问题：
  • 三维盛水问题（需用单调栈）
  • 找容积大于k的容器对数量（双指针+滑动窗口）
• 实际应用：资源分配优化、物理容器设计、股票分析（最大差值变种）