Leetcode Container With Most Water in Javascript

質問する

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Notice that you may not slant the container.

に近づく

最大水を収容できる2つのコンテナバーが設置された場合、水の隣の面積は?見つければいいです.簡単にまずグローバルを探索する方法で解く.

var maxArea = function(height) {
 let answer = 0;
    for(let i=0; i<height.length; i++){
        for(let j=i+1; j<height.length; j++){
            const hei = Math.min(height[i], height[j]);
            const wid = j-i;
            const area = hei * wid;
            if(area > answer){
                answer = area;
            }
        }
    }
    return answer;
};

2つのfor文ですべての場合の数値幅を検索し、最大値を保存して戻ります.同じ大きさ(height)の配列は2回回転するので,時間複雑度はO(n^2)となる.コードをコミットして成功しました

Runtime: 912 ms, faster than 24.54% of JavaScript online submissions for Container With Most Water.
Memory Usage: 41.7 MB, less than 11.30% of JavaScript online submissions for Container With Most Water.

これは少し遅い方法です.したがって,解決策としてTwo Pointerという方法もある.
デフォルトでは、アレイの両端にポインタを1つずつ指定し、条件の下(どのポインタの高さが高いか)で、その条件の結果に基づいてどのポインタが中央になるかを決定します.

var maxArea = function(height) {
     let answer = 0;
    let forward = 0;
    let backward = height.length-1;
    
    while(forward < backward){
      // 어떤 포인터를 당겨올지 정하는 조건
        if(height[forward] < height[backward]){
            answer = Math.max(height[forward] * (backward-forward), answer);
            forward++;
        }else{
            answer = Math.max(height[backward] * (backward-forward), answer);
            backward--;
        }
    }
    return answer;
};

このように繰り返し文が1つになり、時間の複雑さがO(N)になり、上記の私がやった方法よりも効果的になります.

Runtime: 84 ms, faster than 67.90% of JavaScript online submissions for Container With Most Water.
Memory Usage: 40.8 MB, less than 11.30% of JavaScript online submissions for Container With Most Water.