[LeetCode 해석 및 풀이] 11. Container With Most Water

LeetCode 문제 해석 및 풀이 방법

 

문제 11. Container With Most Water(가장 많은 물을 담는 용기)

바로가기

 

문제 설명

영문

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.

 

한글

당신은 길이 n의 정수 배열 height를 받습니다. n개의 수직 선이 그려져있고, i번째 선의 끝부분은 (i, 0), (i, height[i]) 입니다.

 

두 개의 선과 x축을 용기로 했을 때 용기가 가장 많은 물을 담게되는 2개의 선을 찾으세요.

 

용기가 가장 많이 담을 수 있는 물의 양을 반환하세요.

 

용기를 기울일 수 없다는 것에 유의하세요.

 

제한조건

• n == height.length
• 2 <= n <= 10^5
• 0 <= height[i] <= 10^4

 

입출력 예

입력	출력
[1,8,6,2,5,4,8,3,7]	49
[1,1]	1

 

 

해답 및 해설

파이썬 (Python)

대표적인 2포인트 문제

class Solution:
    def maxArea(self, height: List[int]) -> int:
        max_area = 0
        f = 0
        e = len(height)-1

        while f<e:
            min_h = min(height[f], height[e])
            max_area = max(max_area, min_h*(e-f))

            if height[f] > height[e]:
                e -= 1
            else:
                f += 1
        
        return max_area

 

(증명 나중에 적기 귀류법으로 증명하는 풀이임)

 

(아래는 증명 번역본)

조건: i & j에 두 개의 포인터가 있습니다. h[i] <= h[j]라고 가정합니다.

증명 목표: [i, j]의 하위 범위 내에 더 나은 답이 있는 경우 [i + 1, j] 범위에는 해당 최적 하위 범위가 포함되어야 합니다. (이것은 범위 [i, j - 1]이 그것을 포함할 수 없다는 것을 의미하는 것이 아니라, 범위 [i + 1, j]가 그것을 포함한다는 것을 증명하고 싶을 뿐입니다).

증명:
[i, j]의 하위 범위에 더 나은 답이 있다고 가정하므로 이 최적 범위는 [i + 1, j] 또는 [i, j - 1] 또는 둘 다에 포함되어야 합니다.

[i + 1, j]에는 최적 범위가 포함되어 있지 않지만 [i, j - 1]에는 최적 범위가 포함되어 있다고 가정해 보겠습니다. 그러면 이는 두 가지를 의미합니다.

 

1. 최적의 범위는 [i + 1, j - 1]에 없습니다. 그렇지 않으면 [i + 1, j]에 해당 범위가 포함됩니다.
2. 최적의 범위에는 블록 [i, i + 1]이 포함됩니다(이 부분은 [i, j - 1]에는 존재하지만 [i+1, j]에는 존재하지 않기 때문).

그러나 len(i, j - 1) < len(i, j)이고 범위 [i, j]에서 면적은 h[i]의 높이로 제한됩니다(h[의 경우에도). i] == h[j]). 따라서 [i, j - 1] 범위에서는 모든 기둥이 h[j]보다 짧지 않더라도 최대 면적은 i & j에 의해 형성되는 면적보다 작으며 이는 우리의 가정과 모순됩니다. [i, j]의 하위 범위. 이러한 모순은 [i + 1, j]가 최적의 하위 범위(해당 하위 범위가 존재하는 경우)를 포함함을 의미합니다.

위의 정리에 따르면, h[i] < h[j]일 때마다 포인터 i를 전진시키는 알고리즘을 설계할 수 있습니다.