LeetCode 11. Container With Most Water

문제

LeetCode 11. Container With Most Water

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

Container With Most Water - LeetCode

언어

자바스크립트(JavaScript)

 

접근 방법

1. 조합으로 풀면 복잡도가 O(n^2)로 안 좋다.
2. Two pointer 알고리즘으로 풀어야 하고 더 간단하다.

코드

/**
 * @param {number[]} height
 * @return {number}
 */

var maxArea = function(height) {
    let result = 0;
    let leftPointer = 0;
    let rightPointer = height.length -1;
    while(leftPointer !== rightPointer){
        let w = rightPointer - leftPointer;
        let h = Math.min(height[leftPointer], height[rightPointer]);
        if(w * h > result){
            result = w * h;
        }
        if(height[leftPointer] > height[rightPointer]){
            rightPointer --;
        }else{
            leftPointer ++;
        }
    }
    return result;
};

결과

Runtime: 80 ms, faster than 98.00% of JavaScript online submissions for Container With Most Water.

Memory Usage: 47.8 MB, less than 78.68% of JavaScript online submissions for Container With Most Water.

 

복기

1. 데이터가 연속한데 특정 조건을 만족하는 문제는 복잡도가 O(n)인 문제가 많다. 이를 항상 생각해야 한다.