[LeetCode] Python - 11. Container With Most Water

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

Container With Most Water - LeetCode

생각

투포인터를 잡아서 왼쪽 포인터와 오른쪽 포인터를 갱신해가면서 최대 영역값을 찾았습니다.

이때 언제 왼쪽 포인터와 오른쪽 포인터를 갱신해야하는지에 대한 아이디어 때문에 Greedy 문제로 분류된것 같습니다.

 

물의 영역은 두 막대의 최소 높이에 의해 결정됩니다. 따라서, 막대가 작은쪽의 포인터를 움직여주어 최대 영역인지를 계산해줍니다.

이렇게 진행하다보면 왼쪽 포인터의 높이와 오른쪽 포인터의 높이가 같아질수있는데, 이땐 무엇을 움직여도 상관없습니다. (코드에서 두번째 elif 부분을 아예 else: right-=1 로 해도 동일합니다.)

 

Python Code

class Solution:
    def maxArea(self, height: List[int]) -> int:

        res = 0
        left, right = 0, len(height)-1

        while left < right:
            area = (right-left)*min(height[left], height[right])    
            res = max(res, area)
            if height[left] < height[right]:
                left += 1
            elif height[left] > height[right]:
                right -= 1
            else:
                left += 1
        return res