[Leetcode] 42. Trapping Rain Water (javascript)

1689 ワード

質問する


https://leetcode.com/problems/trapping-rain-water/

問題の説明



黒い棒がn本あれば、収容できる水量(青)が必要です.

解決策


https://leetcode.com/problems/container-with-most-water/
11番と問題解決の方法はあまり違いません.
左欄と右欄から移動させます.
左欄の最大高さ(left max)と右欄の最大高さ(right max)が0であると仮定し、左、右欄のindexが出会う前に繰り返し文を実行します.
一番左側の欄(height[left])と一番右側の欄(height[righ])の高さを比較します.
左のバーが右のバーより高い場合は、
左側のバー(height[left])の高さがleft maxより小さい場合、left maxの高さからheight[left]の高さを減算し、水を加える量.(高い場合はleft maxを更新)
そして左++;あなたに作ってあげます.
逆に、右欄(height[right])の高さがright maxより小さい場合、right maxの高さからheight[right]の高さを減算し、水を加える量.(高い場合はright maxを更新)
そして右-;あなたに作ってあげます.

コード#コード#

var trap = function(height) {
    let left = 0;
    let right = height.length - 1;
    let answer = 0;
    let left_max = 0;
    let right_max = 0;
    
    while(left < right) {
        if(height[left] < height[right]) {
            if(height[left] >= left_max) {
                left_max = height[left];
            } else {
                answer += left_max - height[left];
            }
            left ++;
        } else {
            if(height[right] >= right_max) {
                right_max = height[right]
            } else {
                answer += right_max - height[right];
            }
            --right;
        }
    }
    return answer;
};