[leetcode] 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.

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

문제 접근

완전 탐색의 경우 10000^2 이므로 억단위의 시간 복잡도가 나온다.

때문에 시간 복잡도를 고려하면 복잡도가 n인 알고리즘을 구현 해야한다.

문제를 잘 살펴보면 중간에 큰 막대기에 관계 없이 전체의 물의 저장량이 고정된다.

때문에 우리는 좌우로 범위를 좁혀나가면서 진행하는 sliding window 즉 2 pointer로 문제를 접근한다.

문제 해결 방식

1. 좌우로 줄여나가면서 작은 기둥을 기준으로 높이를 정한다.
2. 좌 우 거리를 구한다.
3. 거리와 높이를 구한다.
4. 위의 작업을 갱신하면서 최댓값을 리턴한다.

EDGE CASE

높이가 동일한 경우에 문제가 발생할 여지가 있다.

그러나 동일할 때는 아무쪽이나 줄여줘도 상관없다.

구체적으로 3 1 100 100 2 3 에서 뒷쪽에서부터 줄이는 것이 유리하다.

그러나 우리는 최댓값을 구한다. 작은 녀석들은 최댓값을 갱신시키지 못한다.

결국엔 큰 녀석들만 중요하다는 이야기이다.

10 1000 500 10 의 경우 어느쪽으로 진행하더라고 500이라는 물의 크기에 도달이 가능하다.

구현

class Solution:
    def maxArea(self, height: List[int]) -> int:
        start = 0
        end = len(height) - 1
        water = 0
        
        # sliding window
        while start < end:
            temp_water = min(height[start], height[end]) * abs(start - end)
            water = max(temp_water, water)
            
            # when start side is smaller than end side!
            if height[start] < height[end]:
                start += 1
            else:
                end -= 1
        
        return water