[LeetCode] 11. Container With Most Water

https://leetcode.com/problems/container-with-most-water/submissions/1912411023/?envType=problem-list-v2&envId=oizxjoit

Container With Most Water - LeetCode

---

최대 넓이의 container를 찾는 문제.

 

brute force로 풀 수야 있는데,

하지만 이렇게 풀면 time out 된다. O(n^2)이다 보니...

class Solution:
    def maxArea(self, height: List[int]) -> int:
        max_cont = -1
        for i in range(len(height)):
            for j in range(i + 1, len(height)):
                width = j - i
                h = min(height[j], height[i])
                cont = width * h
                if max_cont < cont:
                    max_cont = cont
                else:
                    continue
        return max_cont

 

 

양쪽 끝에서 작은 높이의 막대만 움직이면서 풀면 최대 넓이를 구할 수 있다. 

이 경우 복잡도도 O(n)로 제한할 수 있다.

 

현재 쌍의 면적을 best에 반영한 뒤, 그 포인터를 포함하는 더 나은 해가 존재할 수 없는 쪽을 제거하는 방식.

from typing import List
class Solution:
    def maxArea(self, height: List[int]) -> int:
        l, r = 0, len(height) - 1
        best = 0

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

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

        return best