力扣经典150题解析之二十八：盛最多水的容器

力扣经典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. 解题思路

我们可以使用双指针法来解决这个问题：

1. 使用两个指针 left 和 right 分别指向数组的开头和结尾。
2. 计算当前指针所指向的两条线段之间能够容纳的水的容量，即 min(height[left], height[right]) * (right - left)。
3. 将 left 指向的线段和 right 指向的线段中高度较小的那个向内移动，因为向内移动较小的线段，可能会找到更高的线段来容纳更多的水。
4. 继续比较移动后的线段之间的水容量，更新最大水容量。
5. 直到 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 官方网站
• 《算法导论》
• 《程序员面试金典》

感谢阅读

期待下一篇…