LeetCode 11 - Container With Most Water

作者 QIFAN 日期 2017-01-12
LeetCode 11 - Container With Most Water

原题链接: 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 - 1lo + 1 走一轮,那样就需要 $O(n^2)$ 的时间复杂度。

但是!

由于最大面积由短边决定,方便起见用 [i, j] 表示以 ij 可以盛放的水。表示如果 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;
}