[LeetCode | Python] 11. Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amound of water a container can store.
Notice that you may not slant the container.

그림을 보면 쉽게 이해가 가능하다. slant (기울어진) 컨테이너는 안 된다는 것에 유의하자.

 

브루트포스로 풀면 O(n^2)로 시간초과가 날 게 뻔하다.

양쪽 line이 기준이 되므로, 투포인터 방식을 생각할 수 있다!

 

풀이1: Two Pointers

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l = 0
        r = len(height) - 1
        res = 0
        
        while l < r:
            area = (r - l) * min(height[l], height[r])
            res = max(res, area)

            if height[l] < height[r]:
                l += 1
            else:
                r -= 1            

        return res

투포인터 방식으로 O(n), 공간복잡도 O(1)에 풀 수 있다. 

 

위 풀이에서 while 문 안에, 어떤 조건에서 l과 r 포인터를 이동시키는지를 유의해야 한다.

• area의 너비는 (r - l)이므로, 포인터를 이동함에 따라 점점 줄어든다.
• area의 높이는 min(height[l], height[r])로 결정되며, 이는 두 막대 중 더 낮은 막대에 의해 제한된다. 

 

따라서, 면적을 더 키우려면 더 낮은 막대를 이동해야 새로운 가능성을 탐색할 수 있다. 

낮은 막대 쪽을 움직이지 않으면, 넓이를 더 크게 만들 가능성이 없다. 

이렇게 투포인터 방식은 불필요한 계산을 배제하면서, 모든 경우를 탐색하지 않고 최적 해를 보장한다.

 

이에 따라 아래와 같은 조건으로 포인터를 이동하는 것이다. 

            if height[l] < height[r]:
                l += 1
            else:
                r -= 1

 

투 포인터 접근 자체는 떠올리기 어렵지 않다. 

포인터 이동 조건을 정확히 이해하고 풀이하자!