力扣经典150题解析之二十八：盛最多水的容器
1. 介绍
在这篇文章中，我们将解析力扣经典150题中的第二十八题：盛最多水的容器。题目要求找出能够容纳最多水的容器，即找出数组中的两条线段，使得它们与 x 轴构成的容器能够容纳最多的水。
2. 问题描述
给定一个长度为 n 的整数数组 height，数组中每个元素表示垂直线的高度。找出数组中的两个元素，使得它们构成的容器能够容纳最多的水。
3. 示例
示例 1:
输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2:
输入：height = [1,1] 输出：1
4. 解题思路
我们可以使用双指针法来解决这个问题：
- 使用两个指针 left 和 right 分别指向数组的开头和结尾。
- 计算当前指针所指向的两条线段之间能够容纳的水的容量，即 min(height[left], height[right]) * (right - left)。
- 将 left 指向的线段和 right 指向的线段中高度较小的那个向内移动，因为向内移动较小的线段，可能会找到更高的线段来容纳更多的水。
- 继续比较移动后的线段之间的水容量，更新最大水容量。
- 直到 left 和 right 相遇，遍历结束。
5. 算法实现
public int maxArea(int[] height) { int left = 0, right = height.length - 1; int maxArea = 0; while (left < right) { int h = Math.min(height[left], height[right]); int width = right - left; int area = h * width; maxArea = Math.max(maxArea, area); if (height[left] < height[right]) { left++; } else { right--; } } return maxArea; }
6. 复杂度分析
- 时间复杂度：O(n)，其中 n 是数组 height 的长度。双指针遍历一次数组。
- 空间复杂度：O(1)，只使用了常数级的额外空间。
7. 测试与验证
测试用例设计
- 输入数组长度为2，包含两个元素。
- 输入数组长度为3，包含三个元素。
- 输入数组长度为9，包含多个元素。
测试结果分析
根据不同的测试用例，分析算法的输出结果，验证解决方案的正确性和有效性。
8. 总结
通过双指针法，我们可以高效地找出能够容纳最多水的容器，解决了该问题。本文详细介绍了解题思路、算法实现和复杂度分析，希望对读者理解该问题和解决方法有所帮助。
9. 参考文献
- LeetCode 官方网站
- 《算法导论》
- 《程序员面试金典》
感谢阅读
期待下一篇…
