[leetcode] 11. Container With Most Water 파이썬 코드

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

 

Brute Force Approach

문제 난이도가 medium이길래 for문 2개 쓰면 답이 아니겠거니 생각은 했지만, 

for 문을 2개 쓰면 시간 초과가 난다.

class Solution(object):
    def maxArea(self, height):
        maxWater = -1
        for i in range(len(height)):
            for j in range(i+1, len(height)):
                area = (j-i) * min(height[i], height[j])
                maxWater = max(maxWater, area)
        return maxWater

 

Two Pointer

Let's find a linear time solution.

투 포인터를 사용하는데 left pointer는 가장 왼쪽에, right pointer는 가장 오른쪽에 놓는다.

최대 넓이를 구해야 하기 때문에 left pointer와 right pointer가 가장 멀리 떨어진 것이 좋다.

 

height[lp]와 height[rp]를 비교한 후에 더 작은 쪽의 포인터를 shift 한다.

 

class Solution(object):
    def maxArea(self, height):
        lp, rp = 0, len(height)-1
        maxWater = (rp - lp) * min(height[lp], height[rp])

        while lp < rp:
            if height[lp] < height[rp]:
                lp += 1
            else:
                rp -= 1
            maxWater = max(maxWater, (rp - lp) * min(height[lp], height[rp]))
        
        return maxWater

 

 

참고

https://www.youtube.com/watch?v=UuiTKBwPgAo