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 :

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


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