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 amound of water a container can store. Notice that you may not slant the container.
그림을 보면 쉽게 이해가 가능하다. slant (기울어진) 컨테이너는 안 된다는 것에 유의하자.
브루트포스로 풀면 O(n^2)로 시간초과가 날 게 뻔하다.
양쪽 line이 기준이 되므로, 투포인터 방식을 생각할 수 있다!
풀이1: Two Pointers
class Solution:
def maxArea(self, height: List[int]) -> int:
l = 0
r = len(height) - 1
res = 0
while l < r:
area = (r - l) * min(height[l], height[r])
res = max(res, area)
if height[l] < height[r]:
l += 1
else:
r -= 1
return res
투포인터 방식으로 O(n), 공간복잡도 O(1)에 풀 수 있다.
위 풀이에서 while 문 안에, 어떤 조건에서 l과 r 포인터를 이동시키는지를 유의해야 한다.
area의 너비는 (r - l)이므로, 포인터를 이동함에 따라 점점 줄어든다.
area의 높이는 min(height[l], height[r])로 결정되며, 이는 두 막대 중 더 낮은 막대에 의해 제한된다.
따라서, 면적을 더 키우려면 더 낮은 막대를 이동해야 새로운 가능성을 탐색할 수 있다.
낮은 막대 쪽을 움직이지 않으면, 넓이를 더 크게 만들 가능성이 없다.
이렇게 투포인터 방식은 불필요한 계산을 배제하면서, 모든 경우를 탐색하지 않고 최적 해를 보장한다.
