LeetCode Hot 100 - 盛水最多的容器解题思路详解

LeetCode Hot 100 - 盛水最多的容器解题思路详解

题目描述

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

说明：你不能倾斜容器，且 n ≥ 2。

示例

输入: [1,8,6,2,5,4,8,3,7] 输出: 49

解题思路

这是一个经典的双指针问题。我们使用两个指针l和r分别指向数组的首尾，计算当前两个柱子所能形成的面积，并不断移动较短的一边，以期望找到更大的面积。

核心思想

• 容器的面积由两个因素决定：

  • 两根柱子之间的距离（宽）：(r - l)
  • 较矮柱子的高度（高）：Math.min(nums[l], nums[r])

  所以面积为：

  area = Math.min(nums[l], nums[r]) * (r - l)

• 为什么移动较短的柱子？

  因为面积受限于较矮的柱子。如果我们固定较矮的柱子而移动较高的柱子，宽度减小，高度不会增加（仍受制于较矮柱子），所以面积只会变小或不变。因此，只有移动较矮的柱子，才有可能在后续中找到更高的柱子，从而获得更大的面积。

Java代码实现

class Solution { public int maxArea(int[] nums) { int l = 0, r = nums.length - 1; int ans = 0; while (l < r) { int area = Math.min(nums[l], nums[r]) * (r - l); ans = Math.max(area, ans); if (nums[l] < nums[r]) { l++; } else { r--; } } return ans; } }

算法复杂度分析

• 时间复杂度：O(n)，每个元素最多被访问一次。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

总结

本题通过双指针技巧将暴力解法 O(n²) 优化到 O(n)，关键在于理解“移动较短边才可能获得更大面积”这一贪心策略。这是 LeetCode Hot 100 中非常经典的一道题，建议熟练掌握其思想和代码实现。