盛最多水的容器：Swift 解法与思路分析
📌 问题描述
给定一个长度为 n 的整数数组 height，每个元素表示在横坐标 i 处的一条垂直线段的高度。任意两条线段和 x 轴构成一个容器，该容器可以装水，水量的大小由较短的那条线段和两线之间的距离决定。
请你找出其中能够容纳最多水的两条线，并返回它们之间形成容器所能容纳的最大水量。
示例：
输入: height = [1,8,6,2,5,4,8,3,7]
输出: 49
容器的两条边是第 2 条线（高度为 8）和第 9 条线（高度为 7），它们之间的距离是 7，所以最大面积是 min(8,7) * (8 - 1) = 7 * 7 = 49。
🐢 暴力解法（仅供参考）
在讲双指针之前，我们也可以从最朴素的方式思考问题：枚举所有可能的两条线段，计算它们之间可以装多少水，最后取最大值。
这种方式虽然思路直观，但时间复杂度为 O(n^2)，在数据量大时效率很低。
Swift 实现：
func maxAreaBruteForce(_ height: [Int]) -> Int {var maxArea = 0let n = height.countfor i in 0..<n {for j in i+1..<n {let h = min(height[i], height[j])let w = j - ilet area = h * wmaxArea = max(maxArea, area)}}return maxArea
}
虽然简单，但这种方法会超时，不推荐在面试中使用，适合用于验证答案或学习过程中的参考实现。
💡 解题思路
这是一个典型的双指针问题。
我们可以从数组的两端开始，使用两个指针分别指向最左和最右的线段。每次计算它们之间的容器所能容纳的水量，然后移动其中较短的一侧。
移动较短的一侧的原因是：水的高度是由较短的那条线决定的，移动较长的一侧不会获得更大的容积，但移动较短的一侧可能会找到一条更高的线，从而提升水量。
步骤如下：
- 初始化两个指针
left = 0，right = height.count - 1。 - 计算当前的水量：
min(height[left], height[right]) * (right - left)。 - 更新最大水量。
- 移动较短边的指针（如果左边短，则
left += 1，否则right -= 1）。 - 重复上述步骤，直到两个指针相遇。
💻 Swift 代码实现
func maxArea(_ height: [Int]) -> Int {var left = 0var right = height.count - 1var maxArea = 0while left < right {let h = min(height[left], height[right])let w = right - leftlet area = h * wmaxArea = max(maxArea, area)// 移动较短的那一侧if height[left] < height[right] {left += 1} else {right -= 1}}return maxArea
}
📊 时间与空间复杂度分析
-
时间复杂度：O(n)
每个指针最多走一次，所以是线性时间复杂度。 -
空间复杂度：O(1)
只使用了常数级别的额外变量。
✨ 优化建议
这个解法已经是最优解法之一。如果你尝试使用两层 for 循环暴力解法，时间复杂度将会是 O(n^2)，在输入规模较大时效率非常低。而双指针方法能够在线性时间内求解，是在面试中非常推荐的策略。
🧪 测试一下
let test = [1,8,6,2,5,4,8,3,7]
let result = maxArea(test)
print("最大水量是：\\(result)") // 输出 49
🏁 总结
- 本题的核心在于意识到两条边之间的水量只与短边有关，因此采用双指针、移动短边是一种非常聪明且高效的方式。
- 这是 LeetCode 中非常经典的一道题，也能很好地锻炼你的思维方式是否具备“从整体最优转向局部策略”的能力。
如果你喜欢这样的算法题解风格，欢迎点赞、评论或者关注我一起交流 Swift、算法与面试技巧！
)
