Container With Most Water (Medium)

문제

You are given an integer array height of length n. 

There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

 

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. 

In this case, the max area of water (blue section) the container can contain is 49.

Example 2:
Input: height = [1,1]
Output: 1
 
Constraints:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104

 

---

풀이

시간복잡도는 생각 안하고 우선 로직을 짜보기로 했다.

2중 for문을 돌려서 막대기를 한칸씩 옮겨가면서 두 막대기중 짧은 것 ( 그래야 물이 컨테이너 안에 들어가니까 )

그리고 기준 막대의 번호 - 현재 막대의 번호 ( 밑변의 길이 ) 를 곱하면 면적을 구할수 있다.

 

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function(height) {
    var maxwater = 0;
    var water = 0;

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

아마 브론즈 수준 문제였으면 이걸로 정답처리가 됐겠지만 역시나 시간초과가 뜬다.

 

해결책 :

시간복잡도(현재 ( O(n^2) )를 줄이기 위해 투 포인터를 이용 ( O(n^2) )

양 끝에서부터 작은 쪽의 포인터가 이동.

---

답안

/**
 * @param {number[]} height
 * @return {number}
 */
var maxArea = function (height) {
    var maxwater = 0;
    var water = 0;

    // 투 포인터 초기화
    var left = 0;
    var right = height.length - 1;

    while (left < right) {
        water = (right - left) * Math.min(height[right], height[left]);
        maxwater = Math.max(maxwater, water);

        // 더 작은 포인터 이동
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxwater;
};