Container With Most Water
음이 아닌 정수 목록 height가 주어집니다. i번째 선은 위치 i에 서 있는 높이 height[i]의 수직 벽입니다. 임의의 두 선은 바닥과 함께 용기를 이루며, 이 용기에 담을 수 있는 물의 양은 두 선 중 더 낮은 선의 높이에 두 선 사이의 거리를 곱한 값입니다. 다른 선들은 방해가 되지 않습니다. 선 한 쌍이 담을 수 있는 최대 물의 양을 반환하세요.
함수
- heightinteger-array
- 위치 0, 1, 2 등의 줄 높이
- 반환값integer
- 두 줄에 담을 수 있는 최대 물의 양
제약 조건
2 ≤ height.length ≤ 1040 ≤ height[i] ≤ 104- 정답은 최대 108이므로 32비트 정수에 들어갑니다.
예제
- 입력
- height = [3, 7, 2, 5, 4, 7, 3, 6]
- 출력
- 36
- 설명
- 위치 1과 7에 있는 높이 7과 6의 선들은 간격이 6이며, 6 × 6 = 36을 담습니다. 가장 높은 두 선인 위치 1과 5의 7은 7 × 4 = 28만 담습니다.
- 입력
- height = [4, 4]
- 출력
- 4
- 설명
- 두 줄은 정확히 하나의 컨테이너를 만듭니다. 높이는 4이고 너비는 1이므로, 4를 담습니다.
후속 질문
여기서는 두 선 사이의 선들은 무시됩니다. 모든 선이 단단한 막대라면, 그 사이에 물이 얼마나 고일까요? 이것도 O(n)으로 계산할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
두 바깥쪽 선부터 시작하세요. 이 선들이 가장 넓은 컨테이너를 만듭니다. 양 끝 중 하나를 안쪽으로 옮기면 너비가 1단위 줄어듭니다. 두 선 중 어느 쪽이 이 손실을 만회할 수 있을까요?
물은 더 짧은 선에 의해 제한됩니다. 더 긴 선을 안쪽으로 옮기면 물 높이는 그대로지만 폭이 줄어들므로, 절대 도움이 될 수 없습니다. 더 짧은 선을 교체해야만 나아질 가능성이 있습니다.
양 끝에 각각 포인터를 둡니다. 두 포인터 사이의 물의 양을 측정하고 가장 큰 값을 유지한 다음, 더 짧은 선 쪽의 포인터를 안쪽으로 한 칸 이동합니다. 포인터가 만날 때까지 반복합니다.
풀이
모든 n²/2개의 쌍을 확인하면 10^4개의 선에 대해 5 × 10^7번의 곱셈이 필요합니다. 물의 양은 쌍에서 더 짧은 선에만 달려 있으므로, 어떤 선이 만들 수 있는 가장 넓은 용기의 짧은 쪽이 된 뒤에는 그 선을 사용하는 더 좁은 용기로는 더 나은 결과를 얻을 수 없습니다. 두 포인터를 사용하면 양쪽 끝에서 시작해 한 번만 순회할 수 있습니다.
모든 쌍을 확인하세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
쌍 i < j의 값은 min(height[i], height[j]) × (j - i)입니다. 물은 더 짧은 벽을 넘어 흘러넘치고, 바닥의 너비는 j - i입니다. 모든 쌍을 시도하고 가장 큰 값을 유지하세요.
n개의 선은 n(n-1)/2개의 쌍을 만듭니다. 선이 10^4개일 때 약 5 × 10^7개이며, n이 두 배가 될 때마다 그 수는 네 배가 됩니다.
알고리즘
best를 0으로 설정합니다.- 각
i와 그 뒤에 오는 각j에 대해min(height[i], height[j]) × (j - i)를 계산합니다. best와 해당 값 중 더 큰 값을 유지합니다.best를 반환합니다.
def maxArea(height):
n = len(height)
best = 0
for i in range(n):
for j in range(i + 1, n):
water = min(height[i], height[j]) * (j - i)
best = max(best, water)
return best가장 높은 줄부터
핵심 아이디어
선 i가 용기의 더 짧은 변이라면, 짝이 되는 선은 높이가 같거나 더 높은 선이면 무엇이든 될 수 있습니다. 따라서 그런 용기 중 가장 좋은 용기는 높이가 같거나 더 높은 선 가운데 가장 멀리 있는 선과 짝을 이룹니다.
선을 가장 높은 것부터 가장 낮은 것 순으로 배치합니다. 선 i를 처리할 때는 이미 배치된 모든 선의 높이가 같거나 더 높으며, 가장 멀리 있는 선은 배치된 인덱스 중 가장 왼쪽 또는 가장 오른쪽인 lo 또는 hi입니다. 따라서 선 i가 담을 수 있는 최대량은 height[i] × max(i - lo, hi - i)이고, 가장 짧은 선을 처리할 때 최적의 용기를 셉니다. 높이가 같은 두 선 중에서는 나중에 배치된 선이 먼저 배치된 선을 짝으로 볼 수 있습니다.
첫 번째 예시에서는 위치 1과 5의 7이 먼저 와서 28을 담습니다. 그다음 위치 7의 6은 lo = 1을 보고 36을 담습니다. 정렬에는 O(n log n) 시간이 들고 O(n) 메모리를 사용합니다.
알고리즘
- 인덱스를 높이 기준으로 내림차순 정렬합니다.
lo와hi를 해당 순서의 첫 번째 인덱스로 설정하고,best를 0으로 설정합니다.- 다음 각 인덱스
i에 대해height[i]에i - lo와hi - i중 더 큰 값을 곱하고, 최선의 값을 유지합니다. lo와hi를 업데이트하여i를 포함합니다.best를 반환합니다.
def maxArea(height):
# Indices from the tallest line to the shortest.
order = sorted(range(len(height)), key=lambda i: height[i], reverse=True)
lo = hi = order[0] # leftmost and rightmost index among the lines placed so far
best = 0
for i in order[1:]:
# Every placed line is at least as tall as line i, so line i is the
# shorter side, and its best partner is the placed line farthest away.
best = max(best, height[i] * max(i - lo, hi - i))
lo = min(lo, i)
hi = max(hi, i)
return best양쪽 끝에서 시작하는 두 포인터
핵심 아이디어
가장 넓은 컨테이너인 left = 0 및 right = n-1에서 시작하고, height[left] ≤ height[right]라고 해 보겠습니다. 선 left를 사용하는 다른 모든 컨테이너는 더 가까운 선과 짝을 이루므로 너비가 더 좁고 height[left]보다 높이가 높지 않습니다. 그중 어느 것도 측정한 물의 양을 넘어설 수 없으므로 선 left는 탐색을 마쳤고, left는 오른쪽으로 한 칸 이동합니다. 높이가 같으면 두 선 모두 탐색을 마친 것이므로 어느 쪽을 이동해도 괜찮습니다.
각 단계에서 선 하나를 제외하므로 n-1단계 후에 포인터가 만납니다. 최선의 쌍을 건너뛰는 일은 없습니다. 두 선 중 먼저 제외되는 선이 있을 때, 그 순간 측정한 컨테이너에는 적어도 그만큼의 물이 담깁니다.
첫 번째 예시에서는 위치 0과 7에 물이 21만큼 담기고 3이 제외됩니다. 위치 1과 7에는 36만큼 담기고 6이 제외됩니다. 나머지 경우에는 각각 15, 28, 12, 10, 2만큼 담깁니다.
알고리즘
left = 0,right = n-1,best = 0으로 설정합니다.left < right인 동안min(height[left], height[right]) × (right - left)를 계산하고 최댓값을 유지합니다.height[left] < height[right]이면left를 오른쪽으로 한 칸 이동합니다. 그렇지 않으면right를 왼쪽으로 한 칸 이동합니다.- 포인터가 만나면
best를 반환합니다.
def maxArea(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
water = min(height[left], height[right]) * (right - left)
best = max(best, water)
# The shorter line cannot do better with any line closer in, so drop it.
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
함정과 경계 사례
- 더 높은 선을 이동하는 것. 첫 번째 예시에서 36 대신 21이 나오는 이유는 7번 위치의 6이 1번 위치의 7과 만나기도 전에 떠나기 때문입니다.
- 더 높은 선이나 두 선의 평균을 높이로 사용하는 것. 물은 더 낮은 벽을 넘어 흘러나오므로 높이는 최솟값입니다.
- 너비를
j - i + 1로 측정하는 것.i와j위치의 선은j - i만큼 떨어져 있으므로[4, 4]는 8이 아니라 4를 담습니다. - 정답이 가장 높은 선들이나 양 끝의 선 쌍을 사용한다고 가정하는 것. 첫 번째 예시에서 두 개의 7은 28을 담고 양 끝의 선 쌍은 21을 담지만, 정답은 36입니다.
자주 묻는 질문3
Container With Most Water의 시간 복잡도는 얼마인가요?
두 포인터 해법은 각 단계에서 포인터 하나를 안쪽으로 한 칸 이동하므로 O(n) 시간과 O(1) 추가 공간이 필요합니다. 모든 쌍을 확인하면 O(n²)이 걸리고, 높이를 기준으로 선을 정렬하면 O(n log n)이 걸립니다.
더 짧은 선에서 포인터를 움직이는 이유는 무엇인가요?
물의 높이는 더 짧은 선에 의해 제한됩니다. 그 선을 유지하면서 만들 수 있는 다른 어떤 용기도 짝이 되는 선이 더 안쪽에 있으므로 더 좁고 더 높지 않습니다. 그중 어느 것도 측정한 용기보다 나을 수 없으므로, 더 짧은 선은 답을 잃지 않고 제외할 수 있습니다.
가장 많은 물을 담는 컨테이너 문제는 그리디 문제인가요?
맞습니다. 각 단계에서 되돌리지 않는 국소적인 선택을 합니다. 더 짧은 선을 버리는 것입니다. 이 선택이 안전한 이유는 제외되는 모든 컨테이너가 이미 측정한 컨테이너보다 나을 수 없기 때문입니다. 그래서 이 문제는 그리디와 투 포인터 모두에 해당합니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def maxArea(height):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
인자
height = [3, 7, 2, 5, 4, 7, 3, 6]
예상 출력
36