Container With Most Water

2026-03-11

---

오늘의 문제는 neetcode의 Container With Most Water이다

heights의 배열이 주어지면 가장 큰 면적의 물을 담길 수 있는 크기를 리턴하면 된다.

 

이 문제를 풀 때 고려해야 하는 것은 양쪽 height가 다르다면 작은 수가 기준이 된다. 

물을 해당 컨테이너에 넣는다고 가정하면 한쪽만 높아서 되는 게 아니기 때문이다. 

 

브루트포스 방식으로 풀면 간단하지만 시간 복잡도가 O(n^2)이 된다.

투 포인터를 사용하면 시간복잡도가 O(n)이며 효율적이게 값을 구할 수 있다.

class Solution {
    public int maxArea(int[] heights) {
        int l = 0, r = heights.length - 1;
        int max = 0;
        while(l < r){
            int wid = r - l;
            max = Math.max(max, Math.min(heights[l], heights[r]) * wid);
            if(heights[l] < heights[r]){
                l++;
            }else{
                r--;
            }
        }
        return max;
    }
}

 

투 포인터에서 어떤 포인터를 옮길지에 대한 기준은 어떤 포인터의 값이 작은가이다. 

한쪽만 값이 높더라도 다른 값이 작으면 그 만큼 면적이 줄어들게 되어 있다.

 

먼저 각 포인터들을 가장 끝에 두어 width를 최대로 하고 포인터를 안으로 이동하며

가장 넓은 면적을 구한다.