双指针

盛最多水的容器

中等#11Java时间 O(n)空间 O(1)

题目要做什么

从非负高度数组中选择两根竖线,与横轴围成容器,求容器能盛水的最大面积。

题目示例输入height = [1,8,6,2,5,4,8,3,7]
题目示例输出49

01 为什么这样做

面积由较短的线和宽度决定。宽度逐渐缩小时,移动较高的线不会提高当前短板;移动较短的线才有机会找到更大的面积。

始终成立的条件

每次淘汰的短边无法与区间内其他位置组成更优答案。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public int maxArea(int[] height) {3        int left = 0, right = height.length - 1, best = 0;4        while (left < right) {5            int area = Math.min(height[left], height[right]) * (right - left);6            best = Math.max(best, area);7            if (height[left] < height[right]) left++;8            else right--;9        }10        return best;11    }12}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索