Container With Most Water

[Leetcode] 11. Container With Most Water

문제

길이가 n인 정수배열 height가 주어졌을 때 i번째의 기둥 라인을 기준으로
x축의 수직선을 그었을 때, 가장 많은 물을 담을 수 있는 양을 반환하라

풀이

이 문제는 보자마자 쉽게 풀 수 있었다.
이전에 각 기둥사이에 얼마만큼 물이 들어있는지 구하는
문제가 있었는데 그 덕분인지 바로 어떻게 풀어야 할 지 떠올랐다.
두 문제가 풀이의 핵심은 같아서 이 문제를 먼저 풀었으면 어려웠던 문제를
더욱 쉽게 빨리 접근할 수 있었지 않았을까 하는 아쉬움이 있었다.

height의 양 끝 인덱스를 가르키는 변수 front와 back을 두고
두 기둥 사이의 넓이를 구해서 tmp 변수에 임시 저장한 후
지금까지 가장 넓은 크기를 저장하고있는 ans 와 비교하여 더 큰 값을 저장한다

다음으로 이동 할 때 front 와 back 중 높이가 더 작은 인덱스를 이동시킨다.

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l = len(height)
        front = 0
        back = l - 1
        f_max = height[0]
        b_max = height[-1]
        ans = 0

        for i in range(l):
            if (front == back): break

            # front 인덱스가 가르키는 높이가 커졌을 경우 새로 갱신
            if (f_max < height[front]): f_max = height[front]

            # back 인덱스가 가르키는 높이가 커졌을 경우 새로 갱신
            if (b_max < height[back]): b_max = height[back]

            # 두 기둥사이의 넓이 계산
            tmp = min(f_max, b_max) * (back - front)

            # 이전에 구했던 넓이 중 가장 크다면 새로 저장
            ans = max(ans, tmp)

            # 둘 중 높이가 더 낮은 인덱스를 이동시킴
            if (height[front] >= height[back]): back -= 1
            else: front += 1
            
        return ans