原题链接: 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)$ 。
代码: