LeetCode 11 - Container With Most Water

题干

给定一组非负的数字 $a_1$ ， $a_2$ ， $a_3$ … $a_i$ ，分别代表坐标轴上的点 $(i, a_i)$ ，假设 $a_i$ ， $a_j$ 以及 x 轴构成了一个木桶，求最大能盛放的水的体积。

思路

题目理解错误，我一直把最大体积理解为了 $a_i$ ， $a_j$ 和 x 轴围成的梯形面积。其实简单点，最大体积就是取决于最短的长度。概括要求就是，两条边相隔尽可能远，两边的最小高度尽可能大。

让我们从底最长开始，也就是左边界 lo = 0 ，右边界 hi = nums.length - 1 。一般情况下，应该让 lo 从小到大走一轮， lo 每次移动的同时， hi 也应该从 nums.length - 1 到 lo + 1 走一轮，那样就需要 $O(n^2)$ 的时间复杂度。

但是！

由于最大面积由短边决定，方便起见用 [i, j] 表示以 i 和 j 可以盛放的水。表示如果 nums[lo] < nums[hi] ，可以肯定 [lo, hi] > [lo, hi - 1], [lo, hi - 2] ... 因为此时 S = lo * (hi - lo) 。 lo 保持不变， hi 最大便可保证最大，所以 lo 可以直接向前（lo++）。
同理如果 nums[lo] > nums[hi] ，可以越过 hi 不变的所有 lo ，让 hi 往下走（hi--）。
这样子时间复杂度就变成了 $O(n)$ 。

代码：

public int maxArea(int[] height) {
    int max = 0;
    int lo = 0;
    int hi = height.length - 1;
    while (lo < hi) {
        if (height[lo] < height[hi]) {
            max = Math.max(max, (hi - lo) * height[lo]);
            lo++;
        } else {
            max = Math.max(max, (hi - lo) * height[hi]);
            hi--;
        }
    } 
    return max;      
}

题干
思路

LeetCode 11 - Container With Most Water

题干

思路

FEATURED TAGS

FRIENDS