Leetcode Python - 11. Container With Most Water

Leetcode #11 - Container With Most Water

이번에는 특정 챕터별로 문제들을 풀어보겠습니다. string을 집중적으로 풀어보겠습니다.

리트코드의 문제 11 ‘Container With Most Water’을 파이썬으로 풀어 보도록 하겠습니다.

discuss를 보도록 하겠습니다.

포인트는 양쪽 끝에서부터 한 칸 한 칸씩 사이를 좁혀가며 최대값을 구하는 것입니다.

전체 코드는 아래와 같습니다.

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

시간복잡도는 O(n) : while문 한 번 순회 공간복잡도는 O(1) : 상수 l,r,maxSum 선언