[LeetCode] 11. Container With Most Water

[Medium] 11. Container With Most Water

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

Example

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

문제 설명

가장 넒게 물을 담을 수 있는 2개의 포인트를 찾아야 한다.

나의 풀이 - 392ms

O(N^2) : 단순 이중 for loop를 이용해 최대 넓이를 구해 리턴했다.

public int maxArea(int[] height) {
        int max_result = 0;
        for(int i = 0; i < height.length-1; i++){
            int f_val = height[i];
            
            for(int j = i+1; j < height.length; j++){
                int s_val = height[j];
                int cont = 0;
                if(f_val < s_val){
                    cont = (j - i) * f_val;
                }else{
                    cont = (j - i) * s_val;
                }
                
                if(max_result < cont){
                    max_result =  cont;
                }
            }
        }
        return max_result;
    }

Best 풀이 - 2ms

O(N) : 양 쪽에 포인트를 둔 후에, 각 포인트 중 작은 값만 이동시키며 최대 값을 확인한다.

public int maxArea(int[] height) {
        int max_val = 0;
        int left = 0;
        int right = height.length - 1;
        
        while(left < right){
            max_val = Math.max(max_val, (right-left)*Math.min(height[left], height[right]));
            if(height[left] < height[right]){
                left++;
            }else{
                right--;
            }
        }
        return max_val;
    }