11. 盛最多水的容器*
最新回答
恃宠拢权
2026-10-20 20:14:58
该代码用于解决“盛最多水的容器”问题，其核心思想是双指针法，通过动态调整左右边界来寻找最大面积。以下是代码的详细解析：
代码解析初始化指针与结果变量
i 和 j 分别初始化为数组的首尾索引，表示容器的左右边界。
res 用于存储当前找到的最大面积，初始值为 0。
循环调整边界
计算当前面积：在每次循环中，计算当前左右边界形成的容器面积 (j - i) * min(height[i], height[j])，并更新 res 为较大值。
移动较短边界：比较 height[i] 和 height[j]：
若 height[i] 更小，则左边界右移（i += 1），因为移动较长的右边界不会增加面积（高度受限于较短的左边界）。
反之，右边界左移（j -= 1）。
终止条件
当左右指针相遇（i >= j）时，循环结束，此时已遍历所有可能的边界组合。
- 双指针法的正确性：每次移动较短边界，虽然宽度减小，但可能通过遇到更高的边界增加面积。若移动较长边界，宽度和高度均可能减小，因此无需考虑。
- 时间复杂度：O(n)，仅需一次遍历。
- 空间复杂度：O(1)，仅使用常数空间。
假设输入 height = [1,8,6,2,5,4,8,3,7]：
- 初始 i=0, j=8，面积为 min(1,7)*8=8。
- 移动左指针（height[0]=1 < height[8]=7），i=1，面积为 min(8,7)*7=49。
- 移动右指针（height[8]=7 > height[1]=8 不成立），j=7，面积为 min(8,3)*6=18。
- 继续调整直到 i=j，最终最大面积为 49。
该算法通过贪心策略高效地缩小搜索范围，确保在 O(n) 时间内找到最优解。核心在于每次排除不可能成为最大面积的边界，避免不必要的计算。
热门标签
