[LeetCode 75] Medium - 11. Container With Most Water ☆

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.

 

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 <= 10^5
• 0 <= height[i] <= 10^4

 

문제 설명

이 문제는 가장 많은 물을 담을 수 있는 두 선을 찾는 문제입니다. 주어진 height 배열은 각 선의 높이를 나타내며, 배열의 인덱스는 x 좌표를 나타냅니다.

문제 조건

1. 두 선 사이의 영역을 x축과 함께 직사각형 모양의 컨테이너로 간주합니다.
2. 컨테이너의 면적은 다음과 같이 계산됩니다:
   • 높이: 두 선 중 낮은 선의 높이.
   • 너비: 두 선의 x 좌표 차이.
3. 면적은 다음 식으로 표현됩니다: 면적 = min⁡(height[left],height[right]) × (right−left)
4. 목표는 가능한 모든 두 선 중에서 가장 큰 면적을 찾는 것입니다.

문제 풀이

브루트 포스 접근법 (비효율적)

1. 모든 가능한 두 선의 조합을 탐색.
2. 각 조합의 면적을 계산하고 최대 면적을 갱신.
3. 시간 복잡도: O(n^2). 큰 입력에서는 비효율적.

효율적인 풀이: 투 포인터 접근법

• 아이디어:
  1. 배열의 양 끝에서 시작하는 두 포인터(left, right)를 사용합니다.
  2. 두 포인터 사이의 면적을 계산한 뒤, 낮은 높이의 포인터를 안쪽으로 이동시킵니다.
  3. 이렇게 하면 더 넓은 너비와 더 높은 높이를 조합할 가능성을 탐색합니다.
• 왜 투 포인터가 가능한가?
  • min⁡(height[left],height[right]) 가 면적의 높이를 결정합니다.
  • 낮은 선을 이동시키는 것은 더 높은 선과의 조합으로 더 큰 면적을 만들 가능성을 탐색하기 때문입니다.

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

        while left < right:
            # 현재 두 포인터로 계산한 면적
            current_area = min(height[left], height[right]) * (right - left)
            # 최대 면적 갱신
            max_area = max(max_area, current_area)

            # 낮은 높이를 가진 포인터를 안쪽으로 이동시켜 더 큰 면적을 탐색 함
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area

 

시간 및 공간 복잡도

1. 시간 복잡도:
   • O(n): 두 포인터가 배열을 한 번 순회합니다.
2. 공간 복잡도:
   • O(1): 추가 메모리 사용이 없습니다.

요약

• 이 문제는 투 포인터를 사용하여 효율적으로 해결할 수 있습니다.
• 시간 복잡도는 O(n), 공간 복잡도는 O(1)로, 매우 큰 입력에서도 성능이 우수합니다.
• 낮은 높이의 포인터를 이동시키는 아이디어가 핵심입니다.

 

 

낮은 높이의 포인터를 이동시켜도, 길이가 줄어들면 의미없는 행동이 되지 않을까?

좋은 지적입니다! 길이가 줄어들면 면적이 감소할 가능성이 생기지만, 낮은 높이의 포인터를 이동시키는 것이 여전히 유효한 이유를 설명하겠습니다.

---

핵심 아이디어

• 면적 공식:면적 = min⁡(height[left],height[right]) × (right−left)
  • 면적은 "높이"와 "너비"의 곱으로 결정됩니다.
  • 여기서 너비(right - left)는 항상 감소합니다. 즉, 더 큰 면적을 만들려면 높이를 더 크게 만들어야 합니다.
• 낮은 높이의 포인터를 이동하는 이유:
  • 현재 두 포인터로 계산한 면적에서, 낮은 높이는 더 이상 최대 면적에 기여할 가능성이 없습니다.
  • 낮은 높이를 이동시켜 더 높은 선을 찾으면, 너비가 줄어드는 만큼 높이를 보상하여 더 큰 면적을 만들 가능성이 생깁니다.

---

왜 낮은 높이를 이동해야 하는가?

1. 낮은 높이의 한계

• 현재 min(height[left],height[right])가 면적의 높이를 결정합니다.
• 따라서, 낮은 높이를 가진 포인터는 현재 면적을 증가시키는 데 장애물이 됩니다.
• 낮은 높이의 포인터를 유지해도, 다른 포인터를 이동하더라도 면적은 감소할 뿐입니다.

2. 높은 높이의 잠재력

• 낮은 높이의 포인터를 이동시키면 더 높은 선을 만날 가능성이 있습니다.
• 이 경우, 너비가 줄어들더라도 높이가 증가하면 더 큰 면적을 만들 수 있습니다.
• 두 포인터를 이동할 때마다 너비는 줄어들지만, 낮은 높이를 이동시키는 것이 더 큰 면적을 찾는 가장 효율적인 방법입니다.
• 높은 선을 유지하면서 너비가 줄어들 때 더 큰 면적을 찾을 가능성이 있기 때문입니다.

3.그래서 낮은 높이의 포인터를 이동해야 하는 이유는?

• 낮은 높이는 현재 면적의 병목 요소입니다.
• 낮은 높이를 이동하면, 더 높은 선을 만나 더 큰 면적을 만들 가능성을 열어줍니다.
• 높은 선을 이동시키면, 높이는 감소하거나 유지되지만 너비만 감소하여 면적이 더 작아질 가능성이 큽니다.

4. 결론

낮은 높이를 이동시키는 이유는, 더 높은 높이를 만나 더 큰 면적을 만들 가능성을 추구하기 위함입니다. 따라서, 높이와 너비의 균형을 최적화하는 데 이 전략이 유효합니다. 😊

 

 

참고 강의

 

https://youtu.be/UuiTKBwPgAo?si=7-YcznSv524Ni7o3