11. Container With Most Water

[hwangnk1004]

11. Container With Most Water

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

[hwangnk1004]

첫 번째 접근

시간 복잡도 : n^2 접근 : 이중 포문을 통해, 배열의 처음 인덱스와 그 다음 인덱스 부터 차례대로 직사각형의 면적을 구함. 결과 : N의 범위가 10^5 까지로 시간 초과 발생 코드 :

public static void solve(int[] arr) {
    int max = 0;

    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            int height = Math.min(arr[i], arr[j]);
            max = Math.max(max, (j - i) * height);
        }
    }
        return max;
}

두 번째 접근

시간 복잡도 : O(n) 접근 : 처음 인덱스와 마지막 인덱스를 가리키는 포인터를 만들어, 면적을 구하면서 조건에 따라 포인터를 옮김. 결과 :

코드 :

public static void solve(int[] height) {
    int size = 0;
    int left = 0;
    int right = height.length - 1;

    while (left < right) {
        size = Math.max(size, (right - left) * Math.min(height[right], height[left]));
        if (height[right] < height[left]) {
            right--;
        } else {
            left++;
        }
    }
    return size;
}

다른사람 풀이

다른 사람들도, 거의 두 번째 방법으로 구현함.