11. Container With Most Water

Loading...LeetCode

基本思路很简单，左右两个指针对向移动，一边移动一边比较当前 container ，关键是：

1. 左右指针分别的移动条件

2. 停止移动的条件

左右两指针，肯定是移动其中比较短的，去找更长的，由此可以得到指针移动判定是比较l,r的大小。而如果剩下的vertical lines里面没有比目前两个边界更长的，那肯定无法形成更大 container 了，也就不需要继续移动。

先开始用queue写的，能过但很慢。试了下直接用index指针，不去做停止判断，直接遍历完整个数组，反而快了很多，看来 test cases 里面 worst case 很少...

queue

class Solution:
    def maxArea(self, height: List[int]) -> int:
        q = collections.deque(height)
        l, r, w = q.popleft(), q.pop(), len(q)+1
        res = w * min(l, r)
        
        while q and min(r, l) < max(q):
            if r <= l and r < max(q):
                r = q.pop()
                w -= 1
            elif l < r and l < max(q):
                l = q.popleft()
                w -= 1
            res = max(res, w * min(l, r))
            
        return res

index double pointer

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r, w = 0, len(height) - 1, len(height) - 1
        res = 0
        
        for w in range(w, 0, -1):
            if height[l] < height[r]: 
                res, l = max(res, height[l] * w), l + 1
            else: 
                res, r = max(res, height[r] * w), r - 1
                
        return res