[리트코드] 11 - Container With Most Water

11. Container With Most Water

Medium

---

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 amount of water a container can store.

Notice that you may not slant the container.

 

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

 

Constraints:

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

분류

배열, 투 포인터, 그리디

---

문제 풀이

문제 분석

이 문제는 수직선들의 높이를 나타내는 정수 배열 height가 주어졌을 때, 두 개의 선을 선택하여 x축과 함께 컨테이너를 만들었을 때 담을 수 있는 물의 최대량을 구하는 문제입니다.

• 입력: 길이가 n인 정수 배열 height (2 ≤ n ≤ 100,000, 0 ≤ height[i] ≤ 10,000)
• 출력: 컨테이너가 담을 수 있는 최대 물의 양 (정수)
• 제약 조건: 컨테이너는 기울일 수 없으므로, 물의 높이는 두 선 중 낮은 쪽의 높이로 결정됩니다. 너비는 두 선의 인덱스 차이입니다. 즉, i, j를 선택했을 때 면적 = (j - i) * min(height[i], height[j])입니다.

---

접근 방법

이 문제를 해결하기 위해 투 포인터(Two Pointer) 알고리즘과 탐욕법(Greedy) 아이디어를 사용했습니다.

• 이유: 배열의 양 끝에서 시작하여 안쪽으로 포인터를 이동시키면서 최대 면적을 갱신합니다. 브루트 포스(모든 쌍 확인)는 O(N²)로 시간 초과가 발생하므로, O(N)에 풀 수 있는 투 포인터가 필수적입니다.
• 핵심 통찰: 현재 두 포인터가 가리키는 선 중 높이가 낮은 쪽 포인터를 이동시켜야만 더 큰 면적을 기대할 수 있습니다. 높은 쪽을 이동시키면 너비만 줄어들고 높이는 여전히 낮은 쪽에 의해 제한되기 때문입니다.

---

구현 설명

1. 변수 초기화

• answer: 최대 면적을 저장할 변수, 0으로 초기화합니다.
• left: 배열의 시작 인덱스(0)를 가리키는 왼쪽 포인터입니다.
• right: 배열의 마지막 인덱스(len(height) - 1)를 가리키는 오른쪽 포인터입니다.

2. 반복문으로 포인터 이동하며 최대 면적 갱신

• while left < right: 조건으로 두 포인터가 만나기 전까지 반복합니다.
• 현재 컨테이너의 면적은 (right - left) * min(height[left], height[right])로 계산합니다.
• answer = max(answer, 현재_면적)을 통해 지금까지의 최대값을 유지합니다.

3. 높이가 낮은 쪽 포인터 이동 (탐욕적 선택)

• if height[left] > height[right]: 이면 오른쪽 선이 더 낮으므로 right -= 1하여 오른쪽 포인터를 왼쪽으로 한 칸 이동시킵니다.
• else: (왼쪽 선이 낮거나 같으면) left += 1하여 왼쪽 포인터를 오른쪽으로 한 칸 이동시킵니다.
• 이동 이유: 낮은 쪽을 움직여야만 더 높은 선을 만날 가능성이 생겨 면적이 커질 수 있습니다. 높은 쪽을 움직이면 너비만 줄어들고 높이는 변하지 않거나 더 낮아져서 면적이 절대 커질 수 없습니다.

4. 결과 반환

• 반복문이 종료되면(left >= right) 모든 유효한 쌍을 확인한 것이므로 최종 answer를 반환합니다.

---

⏱복잡도 분석

• 시간 복잡도: O(N)
  • 두 포인터(left, right)가 각각 배열의 양 끝에서 시작하여 중앙으로 이동하며 최대 한 번씩만 방문합니다. 전체 원소 수 N에 비례하는 연산만 수행하므로 선형 시간입니다.
• 공간 복잡도: O(1)
  • 포인터 변수(left, right)와 최대값 저장 변수(answer) 등 상수 개수의 변수만 사용하므로 입력 크기와 무관하게 일정한 메모리를 사용합니다.

---

핵심 포인트

1. 투 포인터 전략: 양 끝에서 시작해 안쪽으로 좁혀오며 탐색 범위를 효율적으로 줄입니다.
2. 낮은 쪽 포인터 이동 원칙: 현재 컨테이너의 높이는 낮은 쪽에 의해 결정되므로, 높은 쪽을 이동해봤자 높이는 높아지지 않습니다. 낮은 쪽을 이동해야 더 높은 선을 만나 면적이 커질 '가능성'이 생깁니다.
3. 탐욕법의 정당성: 지역적으로 최적의 선택(낮은 쪽 이동)을 반복해도 전역 최적해(최대 면적)를 놓치지 않음을 수학적으로 보장할 수 있습니다. (높은 쪽을 고정하고 낮은 쪽만 움직여도, 버려지는 경우들은 이미 현재 면적보다 작거나 같음이 증명됨)

풀이 코드

class Solution:
    def maxArea(self, height: List[int]) -> int:
        answer = 0
        left = 0
        right = len(height) - 1

        while left < right:
            answer = max(answer,(right-left) * min(height[left],height[right]))
            if height[left] > height[right]:
                right -= 1
            else:
                left += 1

        return answer


# 100000