리트코드 - 11. Container With Most Water

https://leetcode.com/problems/container-with-most-water/description/?envType=study-plan-v2&envId=leetcode-75

Container With Most Water - LeetCode

길이 n의 정수 배열 height가 주어지고, n번째 선의 두 끝점이 (i, 0)과 (i, height[i])가 되도록 수직선이 n개 그려져 있다.
x축과 함께 용기를 형성하는 두 개의 선에서 용기에 가장 많은 물이 들어있는 두 개의 선을 찾는다.
용기에 저장할 수 있는 최대 물의 양을 반환한다.

양극단에 위치하는, 두 개의 포인터를 만들어서 가로가 최대일때 넓이를 구한다. 그런 다음 높이가 작은 쪽의 인덱스를 하나씩 중심으로 옮기면서 둘이 만날 때까지 최대 넓이를 갱신한다. 같을 경우 왼쪽을 옮긴다.

그렇게 하면 시간복잡도 O(n)으로 최대 넓이를 구할 수 있다.

 

class Solution:
    def maxArea(self, height: List[int]) -> int:
        start, end = 0, len(height) - 1 # O(1)
        res = 0

        while start < end: # O(n)
            W = end - start # O(1)
            H = min(height[start], height[end]) # O(1)
            res = max(res, W * H) # O(1)

            if height[start] <= height[end]: # O(1)
                start += 1 # O(1)
            else:
                end -= 1 # O(1)

        return res

 

해당 코드의 공간 복잡도는 정수 값만을 위한 변수를 할당하므로 O(1)이다.