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

- 문제 링크: https://leetcode.com/problems/container-with-most-water/

- 난이도: Medium

 

물을 담는 조합 중 가장 많이 담을 수 있는 물의 양을 반환하는 문제다

제일 단순하게는 모든 조합을 확인할 수 있는데 이 경우 시간 복잡도는 O(n^2)가 된다

투포인터를 사용하면 O(n)의 시간복잡도로 해결할 수 있는데, 물의 양은 두 선분중 더 작은 쪽에 의해 결정된다는 것에 착안하면, 양쪽 포인터를 높이가 낮은것만 이동시키는 방식으로 풀면 된다

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        answer = 0
        while left < right:
            area = (right - left) * min(height[left], height[right])
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
            answer = max(answer, area)

        return answer