[Leetcode] 11. Container With Most Water - JS

https://leetcode.com/problems/container-with-most-water/description/?envType=study-plan-v2&envId=top-interview-150

 

 

 

1. 문제 분석

문제분석
--------------------
길이 n으로 구성된 정수 배열 height가 주어진다.
n은 i번째의 (i, 0)에서 (i, height[i])사이의 수직선이다.
두 x축 사이의 공간에서 최대의 물을 담을 수 있는 물의 양을 반환하라.

제한조건
--------------------
- n == height.length
- 2 <= n <= 10^5
- 0 <= height[i] <= 10^4

 

2. 접근 방법

접근방법 - Two pointer
--------------------
물의양을 구하는 방법
시작 인덱스, 끝 인덱스 차이 * 시작 인덱스와 끝 인덱스의 height[i] 값 중 작은 값
투 포인터를 양끝에서 시작하여 현재 인덱스보다 다음 인덱스의 height 값이 크면 인덱스를 옮긴다.

1. 최대 물의양(water),시작 인덱스, 끝 인덱스 각각 0, 0, n-1로 초기화
2. 시작 인덱스 < 끝 인덱스 만족하면 반복
    - height[시작] < height[끝] 만족하면 시작 인덱스 우측 이동
    - height[시작] >= height[끝] 만족하면 끝 인덱스 좌측 이동
    - water = Math.max(water, (끝 인덱스 - 시작 인덱스) * Math.min(height[시작], height[끝]))
3. water 반환

 

 

3. 코드

var maxArea = function(height) {
    let water = 0;
    let start = 0;
    let end = height.length - 1;

    while (start < end) {
        water = Math.max(water, (end - start) * Math.min(height[start], height[end]));
        
        if (height[start] < height[end]) {
            start++;
        } else {
            end--;
        }
    }
    return water
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(1)

 

Two pointer를 활용했다. 양쪽에서 시작 인덱스와 끝 인덱스를 옮겨가면서 최대 넓이를 저장하도록 구현했다.

물의 양을 어떻게 구할 수 있는지를 먼저 생각해봤다. 물의 양(= 직사각형 넓이) 구하려면 가로 X 세로가 있어야 한다.

가로, 세로가 의미하는 것은 무엇이고 이를 최대값으로 구하기 위해 어떻게 할 수 있는지 생각해보면서 접근하니 쉽게 풀 수 있었다.