[LeetCode] 11. Container With Most Water (python)

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

Container With Most Water - LeetCode

 

해당문제는 bruteforce로 풀면 n^2의 시간복잡도가 걸려 시간초과가 난다.

투포인터로 풀면 n의 시간복잡도를 가진다.

이때 이해가 잘안갔던점은 왜 굳이 다음 스텝으로 넘어갈때 길이가 짧은 막대의 인덱스를 넘기는지였다.

즉, height[left] 와 height[right] 중 더 짧은 포인터 를 옮겨 그 다음을 순회하는 점이 이해가 잘 되지않았다.(left라면 left+1 , right 라면 right-1.)

container는 짧은 height 를 기준으로 물이 담아지기 때문에, 짧은 포인터를 옮겨야 그 다음 container의 크기가 커질 가능성이 있기때문이다.

---

SOLUTION CODE

# PYTHON

class Solution:
    def maxArea(self, height: List[int]) -> int:
        # # BRUTE FORCE
        # res = 0

        # for l in range(len(height)):
        #     for r in range(len(height)):
        #         area = (r - l) * min(height[l],height[r])
        #         res = max(res,area)
        # return res

        res = 0
        l, r = 0, len(height) - 1

        while l < r:
            area = (r-l) * min(height[l],height[r])
            res = max(res,area)

            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
        return res