[LeetCode] 11. Container With Most Water

접근

• O(n) 시간복잡도 탐색을 통해 문제에서 요구하는 성능을 만족하는 것이 핵심
•  two pointers 기법을 사용해야 한다.

 

문제 링크

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

 

O(n^2) 시도

TLE: 해당 솔루션은 오답입니다. 

class Solution:
    def maxArea(self, height: List[int]) -> int:
        answer = 0
        left = 0
        height_length = len(height)

        while left < height_length-1:
            
            for i in range(left+1, height_length):
                WIDTH, HEIGHT = i-left, min(height[left], height[i])
                answer = max(WIDTH * HEIGHT, answer)

            left += 1

        return answer

 

솔루션

위 코드는 쉽게 작성할 수 있습니다. TLE임을 확인하고 O(N)으로 풀기 위해 Two pointers 기법을 사용해야 함을 유도할 수 있어야 합니다. 두 기둥 중 높이가 가장 낮은 기둥이 곧 가능한 모든 컨테이너의 높이가 된다는 것을 아는 것이 포인트입니다.

class Solution:
    def maxArea(self, height: List[int]) -> int:
        answer = 0
        height_length = len(height)
        left, right = 0, height_length-1

        while left < right:
            if height[left] <= height[right]:
                answer = max(answer, height[left] * (right-left))
                left += 1
            else:
                answer = max(answer, height[right] * (right-left))
                right -= 1

        return answer