[LeetCode] 11. Container With Most Water 해설 및 풀이 (Python)

LeetCode 11. Container With Most Water

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

 

---

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가 주어집니다. 이 배열의 길이는 n입니다. n개의 수직선이 그려져 있으며, i번째 수직선의 두 끝점은 각각 (i, 0)과 (i, height[i])입니다.

 

이제 이 수직선들 중 두 개를 선택해서, x축과 함께 하나의 용기(컨테이너)를 만든다고 가정합시다. 이 컨테이너는 물을 담을 수 있으며, 가장 많은 양의 물을 담을 수 있는 두 수직선을 선택하는 것이 목표입니다.

기울어지지 않은(수직인) 컨테이너만 고려합니다.

 

용기를 기울이지 않도록 주의하세요 .

입력: 높이 = [1,8,6,2,5,4,8,3,7]
출력: 49
설명: 위의 수직선은 배열 [1,8,6,2,5,4,8,3,7]로 표현됩니다. 이 경우 용기가 담을 수 있는 최대 물 면적(파란색 부분)은 49입니다.

예시 2:

 

입력: 높이 = [1,1]
출력: 1

제약사항:

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

---

문제 유형

정렬
투 포인터
그리디 알고리즘

 

풀이 방법 도출

 

height 배열은 각각 x축 위에 세워진 수직선의 높이를 말합니다.

이 문제는 두 수직선을 골라서 그 사이에 물을 담을 수 있는 컨테이너를 만들었을 때, 가장 많은 물을 담을 수 있는 경우의 면적을 구하는 문제입니다.

면적 계산은 (가로 길이) x (낮은 쪽 수직선의 높이)로 합니다.

 

1. 왼쪽 포인터(left)는 배열 시작점에서, 오른쪽 포인터(right)는 배열 끝점에서 시작합니다.
2. 두 포인터가 가리키는 수직선 사이의 너비와 낮은 쪽 높이로 면적을 계산합니다.
3. 최대 면적을 갱신하며 더 작은 높이의 수직선 쪽 포인터를 이동시킵니다. 더 큰 면적을 얻기 위해선 넓이를 줄이더라도 더 큰 높이를 얻는 것이 중요하기 때문입니다.

 

시간 복잡도

• O(N)

---

 

핵심 코드 삽입 및 설명

 

class Solution:
    def maxArea(self, height: List[int]) -> int:
        # 왼쪽과 오른쪽 포인터 초기화
        left, right = 0, len(height) - 1
        max_area = 0  # 최대 면적 초기화

        # 포인터가 겹치기 전까지 반복
        while left < right:
            # 현재 너비는 두 포인터 사이 거리
            width = right - left
            # 현재 높이는 두 수직선 중 더 낮은 값
            current_height = min(height[left], height[right])
            # 현재 면적 계산
            current_area = width * current_height
            # 최대 면적 갱신
            max_area = max(max_area, current_area)

            # 더 짧은 수직선을 안쪽으로 이동시킴
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area  # 최대 물의 양 반환