【刷穿 LeetCode】11. 盛最多水的容器（中等）
最新回答
避讳真心
2026-10-21 08:05:18
盛最多水的容器问题的最优解法是双指针法，时间复杂度为O(n)，空间复杂度为O(1)。
- 双指针法：
初始化：设置两个指针，一个指向数组的开始（i = 0），另一个指向数组的末尾（j = n - 1）。
计算面积：在每一步中，计算当前两个指针所指向的线构成的容器的面积，即(j - i) * min(height[i], height[j])。
移动指针：比较height[i]和height[j]的值，移动高度较小的那个指针。这是因为移动高度较大的指针不可能得到更大的面积，而移动高度较小的指针有可能找到更高的线，从而可能增加面积。
更新最大面积：在每次计算面积后，更新记录的最大面积。
终止条件：当两个指针相遇时，算法终止。
这种方法确保了在O(n)的时间内找到最大面积，因为它只需要对数组进行一次遍历。同时，它只使用了常数级别的额外空间，因此空间复杂度是O(1)。
- 示例分析：
以输入[1,8,6,2,5,4,8,3,7]为例，初始时i = 0，j = 8，计算面积为min(1, 7) * 8 = 8。
由于height[i] < height[j]，移动i到1，此时面积为min(8, 7) * 7 = 49。
继续这个过程，直到i和j相遇，最终得到的最大面积为49。
这种方法高效且直观，是解决此类问题的经典双指针应用。
热门标签
