Leetcode - 11. Container With Most Water

문제

수조와 칸막이가 주어지고 두개를 선택한다고할때 가장 많은 물을 담을 수 있는 경우, 얼만큼의 양을 담을 수 있는가? 가령 아래의 경우, 최대인경우 높이 7 너비 7로 49만큼의 양을 담을 수 있다.

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49

between height[1] ~ height[7] -> 7 * 7 = 49

해결 O(N^2) -> TLE

당연히 가장 먼저 생각해볼수 있는 쉬운 솔루션은 brute force 방식으로 두개의 막대기를 선택하는 모든 경우의 수를 완전탐색하는것이다. 역시 Time Limited Exeeded발생.

int maxArea(int* height, int heightSize){
    int max_amount = 0;
    int cur_amount = 0;
    
    for (int i = 0; i < heightSize; i++) {
        for (int j = i + 1; j < heightSize; j++) {
            cur_amount = (j - i) * (height[i] < height[j]? height[i]: height[j]);
            if (cur_amount > max_amount)
                max_amount = cur_amount;
        }
    }
    return max_amount;
}

해결 O(N)

left/right 의 two pointer를 어떤조건일때 늘리고 줄여야되는지, 아이디어를 깨닫기 쉽지 않아 discussion을 조금 참고했다.

방법은 매번 반복문마다, left와 right 둘중 작은값을 미리 저장하고, left와 right 둘중에 작은 값의 인덱스를 바로 다음큰값의 인덱스로 이동시키는것. 매번 반복마다 max값을 갱신해서 최종 갱신된 max값을 리턴하면 된다.

#define max(a,b) (((a) > (b)) ? (a): (b))

int maxArea(int* height, int heightSize){
    int max_amount = 0;
    int left = 0;
    int right = heightSize - 1;
    int cur_min_h = 0;
    
    while (left < right) {
        cur_min_h = height[left] < height[right] ? height[left]: height[right];
        max_amount = max(max_amount, (right - left) * cur_min_h);
        /* move the smaller point (between L and R) to the next larger bar */
        while (height[left] <= cur_min_h && left < right) left++;
        while (height[right] <= cur_min_h && left < right) right--;
    }
    return max_amount;
}