[Leetcode][python] 11: Container with most water - Two pointer

문제

• Leetcode 11: Container with most water
• Level: Medium
• Link

Container With Most Water - LeetCode

 

나의 풀이

가로길이는 최대화, 각 인덱스의 원소 값들의 차이는 최소화시키는 것이 관건이다.

처음에는 다음과 같이 brute force로 모든 면적 조합을 계산하여 가장 큰 값을 리턴해주었다. 하지만 시간 초과가 났다. 당연함. n의 최대 값이 100000임.

class Solution:
    def maxArea(self, height: List[int]) -> int:
        maxh = 0
        for i in range(len(height)):
            w = 0
            for j in range(i + 1, len(height)):
                h = min(height[i], height[j])
                w += 1
                if (h * w) > maxh:
                    maxh = h * w
                    
        return maxh

 

Two Pointer로 다시 풀어보았다. 왼쪽의 element가 오른쪽의 element보다 클 때, 그 반대일 때의 경우를 나눠서 최대 면적 값을 갱신해주었다. i == j가 되면 탐색 종료.

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