[leetcode][Medium][Two Pointers] 11. Container With Most Water 풀이, 해설 (python)

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

Container With Most Water - LeetCode

 

1차 풀이 

일단 단순하게, O(n^2)로 접근했다. 그랬더니 시간 초과가 발생했다. 

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        area = - sys.maxsize
        
        # 시간 초과 
        area = - sys.maxsize
        for l in range(len(height)):
            for r in range(l + 1, len(height)):
                area = max(area, (r - l) * min(height[l], height[r]))
                
        return area

 

2차 풀이 

시간 초과를 개선하고자, two-pointer 를 도입했다. 

그런데, 후에 l과 r 좌표를 움직이는 조건이 고민이 되었다. 

l과 r 을 옮기는 방향으로 가로 길이가 줄어드는 만큼, 세로 길이가 높은 방향으로 움직이는 방향으로 진행했다. 

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        
        l, r = 0, len(height) - 1 
        area = - sys.maxsize
        
        while l < r :
            area = max(area, (r - l) * min(height[l], height[r]))

            # 높이가 큰쪽으로 이동 
            if height[l] < height[r]:
                l = l + 1
            else:
                r = r - 1
                
        return area

 

해설

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

 

2차 풀이와 동일한 방법으로 풀었다.