站点图标 Wankko Ree's Blog

[刷题]LeetCode 11. 盛最多水的容器

这题的话都能想到的就是两层for去遍历所有情况捞个最大值,但是这样子的话就没啥意义了,毕竟是来刷算法的。

但是不暴力解又没思路,所以就去看官方题解了。

双指针的写法实际上简单得很,关键是为何能成立。

其中最关键的一步就是较小的那个指针向另一个指针逼近,原因是移动指针之前,储水量是min(h[i], h[j])*(j-i),而假设左边指针的数值更小,那么就是h[i]*(j-i),这时候如果保持左边指针不移动,而去让右边指针来逼近,那么就算右边指针一路逼近到左边指针,期间的最大储水量也被h[i]限制了,因为如果右边指针如果逼近期间有比左边指针的数据大的情况,那储水量还是取决于h[i],并不会有更大的储水量,如果右边指针更小那就更不可能了。

所以让数据较大的指针去逼近是没有意义的,那就只能让数据较小的指针去逼近较大的。

所以代码如下。

from typing import List

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i = 0
        j = len(height) - 1
        m = 0
        while i < j:
            m = max(m, min(height[i], height[j]) * (j - i))
            if height[i] < height[j]:
                i+=1
            else:
                j-=1
        return m

solution = Solution()
assert solution.maxArea([1,8,6,2,5,4,8,3,7]) == 49
assert solution.maxArea([1,1]) == 1
assert solution.maxArea([4,3,2,1,4]) == 16
assert solution.maxArea([1,2,1]) == 2

执行用时: 216 ms , 在所有 Python3 提交中击败了 22.51% 的用户
内存消耗: 23.3 MB , 在所有 Python3 提交中击败了 96.16% 的用户
通过测试用例: 60 / 60

emm,这耗时感觉有点拉,应该没这么慢才对,于是打算优化一下,比如说数据重复使用之类的就给个变量,然后不用max/min这类函数,反正就俩数比大小,应该还是if更快。

from typing import List

class Solution:
    def maxArea(self, height: List[int]) -> int:
        i = 0
        j = len(height) - 1
        m = 0
        while i < j:
            l, r = height[i], height[j]
            if l < r:
                s = l * (j - i)
                i+=1
            else:
                s = r * (j - i)
                j-=1
            if s > m:
                m = s
        return m

solution = Solution()
assert solution.maxArea([1,8,6,2,5,4,8,3,7]) == 49
assert solution.maxArea([1,1]) == 1
assert solution.maxArea([4,3,2,1,4]) == 16
assert solution.maxArea([1,2,1]) == 2

执行用时: 188 ms , 在所有 Python3 提交中击败了 59.59% 的用户
内存消耗: 23.3 MB , 在所有 Python3 提交中击败了 99.08% 的用户
通过测试用例: 60 / 60


The End
退出移动版