[刷题]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