Saturday, January 24, 2015

[LeetCode]Container with Most Water

又是双指针的问题,我们以下图为例子进行说明:


















首先我们开始的两个指针i,j分别指向1和9,当我们计算过1和9所围成的面积之后,1和剩余所有墙壁所围成的面积都不可能大过和9围成的面积,我们左移1到2,2的高度大于1所以2和9围成的面积有可能大于之前所计算的值。2的高度仍然小于9,根据之前的解释,我们移动2,但是我们没有必要去check 3和4因为3和4的高度比2还要小,面积更小,然后我们移到5,5的高度大于2的高度,有可能面积更大,我们一直这么做直到i >= j。
所以我们的策略是,哪边高度更小,我们移动哪边的指针直到找到一个比当前高度更高的值,然后重复之前的步骤。时间复杂度是O(n),空间复杂度是O(n),代码如下:

No comments:

Post a Comment