[LeetCode][Python3] 11. Container With Most Water

Problem :

https://leetcode.com/problems/container-with-most-water/

My Solution :

class Solution:

def maxArea(self, height):

"""

:type height: List[int]

:rtype: int

"""

ans = 0

i, j = 0, len(height)-1

while i < j:

ans = max(ans, min(height[i], height[j]) * (j - i))

if height[i] < height[j]:

i += 1

else:

j -= 1

return ans

Comment :

코드가 짧아서 이해가 쉬울 것 같은데 전략을 말로 풀어쓰면 이렇다.

면적은 가로와 세로의 곱으로 구할 수 있는데, 가로는 두 막대 간 거리이고, 세로는 두 막대 중 높이가 낮은 것에 의해 결정된다. 양 끝에서 안쪽으로 포인터를 옮겨가며 면적을 계산해볼 것인데, 이때 매번 안쪽으로 이동할 포인터는 둘 중 높이가 낮은 막대 쪽이다. 왜냐하면 높은 막대 쪽 포인터는 아무리 안쪽으로 옮겨봐야 반대쪽 낮은 막대 때문에 사각형의 높이가 더 이상 높아질 수 없다. 대신 옮기면 옮길수록 가로 길이만 줄어들 뿐이다. 따라서 매 단계마다 면적의 최댓값을 갱신하면서 낮은 막대 쪽 포인터만 안쪽으로 한 칸씩 옮겨가며 면적을 계산해보면 된다.