11. Container With Most Water

문제

각 위치의 높이를 나타내는 정수 배열이 주어진다. 두 위치 간 높이에 따른 최대 부피를 계산하는 문제이다.

Constraints:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104

링크

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

Solution 1

class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        int n = height.length;
        for(int i=0;i<n;i++) {
            int h1 = height[i];

            for(int j=i+1;j<n;j++) {
                int h2= height[j];
                if(h1<=h2) {
                    max = Math.max(max, h1*(j-i));
                }
                else {
                    max = Math.max(max, h2*(j-i));
                }
            }
        }
        return max;
    }
}

문제를 읽고 직관적으로 생각한 풀이 방식이다.

• 시간 복잡도: O(n^2)
• 타임 초과 발생!

Solution 2

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

    }
}

부피의 최대를 구하는 문제이다. 부피는 높이와 너비를 고려해야 한다. 높이와 너비는 위치에 따라 변동한다. 따라서 둘 중 하나를 고정시켜서 나머지를 비교 후 후보를 도출하고 고정 요소를 이동시킨다. 이 문제에서 너비(위치)를 고정 요소로 지정하였다. L, R 포인트를 양 끝으로 지정(최대 너비로 시작)하여 높이를 비교하여 정답 후보를 도출하였다.

• 시간 복잡도: O(n)
• L, R 포인트를 사용해서 풀이