Container With Most Water

각 컨테이너는 두 위치 i < j의 쌍입니다. 물은 더 낮은 벽을 넘쳐흐를 때까지 차오르고, 두 벽 사이의 바닥 너비는 j - i이므로 이 쌍이 담을 수 있는 양은 min(height[i], height[j]) × (j - i)입니다. 모든 쌍을 확인하고 가장 큰 값을 유지하면, 정의에 따라 답을 구할 수 있습니다.

문제는 쌍의 개수입니다. n개의 선은 n(n-1)/2개의 쌍을 만듭니다. 선이 10^4개라면 약 5 × 10^7개이고, 목록이 두 배가 될 때마다 그 수는 네 배가 됩니다. 컴파일 언어로는 이를 1초도 안 되는 시간에 처리할 수 있지만, Python, Ruby 또는 R에서는 몇 초가 걸리며, n이 10^5에 이르면 어떤 언어로도 처리하기에는 개수가 너무 빠르게 늘어납니다.

더 짧은 변의 쪽에서 용기를 바라보세요. 선 i가 더 짧은 변이라면, 담기는 물의 양은 height[i]에 거리 값을 곱한 것이며, 짝이 되는 선은 적어도 그만큼 높으면 됩니다. 따라서 i가 더 짧은 변인 경우 만들 수 있는 가장 좋은 용기는, 그보다 높거나 같은 선 중 가장 멀리 있는 선과 짝을 이룹니다.

그런 짝을 빠르게 찾으려면 선들을 가장 높은 것부터 가장 낮은 것 순서로 배치하세요. 선 i를 처리할 때, 그보다 먼저 배치된 모든 선은 높이가 적어도 같으며, 그중 가장 멀리 있는 선은 배치된 인덱스의 가장 왼쪽 또는 가장 오른쪽에 있습니다. 이 두 인덱스 lo와 hi를 추적하면, 선 i가 담을 수 있는 최대 물의 양은 height[i] × max(i - lo, hi - i)입니다. 더 짧은 변을 처리할 때 가장 좋은 용기가 계산되므로, 정답은 이 값들 중 가장 큰 값입니다.

첫 번째 예제에서는 위치 1과 5의 두 7이 먼저 처리되어 28을 담습니다. 다음으로 위치 7의 6이 처리되며, 이때 lo = 1이고 hi = 5이므로 6 × 6 = 36을 담습니다. 이보다 더 짧은 선은 이 값을 넘지 못합니다. 높이가 같은 선들은 어떤 순서로 처리해도 됩니다. 같은 높이인 두 선 중 나중에 처리되는 선은 먼저 처리된 선을 짝으로 볼 수 있습니다.

정렬에는 O(n log n), 순회에는 O(n)이 걸리므로 충분히 빠릅니다. 그래도 순서를 저장하기 위해 O(n)의 메모리가 필요하며, 다음 접근법은 정렬과 메모리를 모두 없앱니다.

가장 넓은 컨테이너인 left = 0과 right = n-1에서 시작해 그 넓이를 계산합니다. 이제 두 선 중 하나를 제외할 수 있으며, 선택은 정해져 있습니다. 더 짧은 선을 제외하세요. height[left] ≤ height[right]라고 해 봅시다. 선 left를 사용하는 다른 모든 컨테이너는 이 선을 right보다 더 가까운 선과 짝지으므로 더 좁고, 높이도 여전히 height[left] 이하입니다. 어느 것도 계산한 물의 양을 넘지 못하므로 선 left는 더 이상 고려할 필요가 없고, left는 오른쪽으로 한 칸 이동합니다. 더 높은 선을 대신 이동하면 높이의 상한은 그대로인 채 너비만 줄어드므로 결과가 더 나빠질 수밖에 없습니다. 두 높이가 같으면 두 선 모두 더 이상 고려할 필요가 없으며, 어느 쪽을 이동해도 괜찮습니다.

각 단계에서 선 하나를 영구적으로 제외하므로, n-1단계가 지나면 포인터가 만납니다. 최선의 쌍을 건너뛰는 일은 없습니다. 두 선 중 하나가 처음 제외되는 순간, 그때 계산한 컨테이너에는 적어도 그만큼의 물이 담깁니다.

[3, 7, 2, 5, 4, 7, 3, 6]에서 위치 0과 7은 3 × 7 = 21을 담습니다. 3이 더 짧으므로 left를 1로 이동합니다. 위치 1과 7은 6 × 6 = 36을 담고, 이제 6이 더 짧으므로 right를 6으로 이동합니다. 그다음 컨테이너들이 담는 물의 양은 15, 28, 12, 10, 2이므로 답은 36으로 유지됩니다.