レトコート‐42:雨水の捕捉

この記事はFOOLISH HUNGRYブログから取得されます.
問題
各々のバーの幅が1である立面図を表しているNの非負の整数を与えられて、雨の後、それがどれくらいの水をトラップすることができるかについて計算します.
例1 :

入力:高さ= [ 0 , 1 , 0 , 2 , 1 , 0 , 1 , 3 , 2 , 1 , 2 , 1 ]
出力:6
説明:上記の標高マップは、(0,1,0,2,1,0,1,3,2,1,2,1)配列で表される.この場合、雨水(青のセクション)の6つの単位は罠にかけられています.
例2 :
入力:高さ= [ 4 , 2 , 0 , 3 , 2 , 5 ]
出力:9
制約
n = =高さ.長さ
1 <= n <= 2 * 104
0 <=高さ[ i ] <= 105
ソース:Leetcode
警告、警告、警告!
あなたはそれを解決しようとする前に解決策を参照してくださいに来ている場合、これは本当にあなたを助けることはありません、約束!その場合は、我々は、戻ってください最初にそれを試してくださいお勧めします.あなたが(少なくとも)1時間の思考と試みの後、それを解決することができないならば、戻ってください!🙂 あなたはそれを解決することができますhere
解決策
我々は、高さ［10、5、20］でA、BとCという名前の3つの昇格だけを持っていると思います.我々が高度5に水を注ぎ続けるならば、それが10に達するまで、それは5の上で残ります.10より上の何でも、以下のショーとして離れて排水されます.

したがって、Bについては、水の有効高さはBの両側に属する最大高さの最小高さである.
言い換えれば、あらゆる標高のために.
有効な高さb = min(max(bの左端へのすべての高さ)、max(bの右側の高さ))
コードにジャンプする前に、効果的な高さとトラップ雨水計算のアイデアのほとんどのシミュレーションを行いましょう.
我々は高さの[ 5 , 5 , 0 , 20 ]以下の5つの標高点を持っていると思います.
申し訳ありませんが、描画ミスに関して申し訳ありませんが、Eの高さはAまたはCに比例しません😛 それは解決策を理解することを傷つけません

標高点から始めましょう.そこにはポイントがありませんので、最大の高さはAの高さです.高さ4 [ 0 , 5 , 0 , 20 ]の右側に4点あります.最大値は20です.従って、左maxと右maxの最小値は10である.従って、有効高さは10−10＝0である.つまり、標高点Aはどんな水もトラップできない.

同様に、Bの左側の最大高さは10であり、Bの右は20である.有効高さはmin(10,20)＝10であり,bは10−0＝10単位の水を捕捉できる.

次の3つの画像は、多くの水C、DとEがトラップすることができます計算を示しています.



したがって、トラップされた水の合計単位は0 + 10 + 5 + 10 + 0 = 25となります.
アルゴリズム
標高点の左と右に最大の高さを見つけるために、我々はその点からループすることができますし、一度左に移動し、再び右に移動します.したがって、これはo(n 2)の実行時複雑さを引き起こします.しかし、我々は余分なスペースを使用していないので、我々は(1)空間の複雑さを取得します.
単純な動的計画を適用して、左と呼ばれる別の配列の配列の先頭から最大値を格納すると、ランタイム複雑さは簡単にO(n)に改善できます.また、配列と同じ配列を右という別の配列で保存できます.その後、我々は標高点の左と右の最大値を知っているたびに、我々は単に左と右の配列をチェックします.
そこで、正式にアルゴリズムは以下の通りです.

i = 0からendまでを開始し、left []配列の最大値を保存します.左[ i ] = max (左[ i - 1 ], height [ i ] ]

のようなことをしなさい

i = endから0に始まり、left []配列の最大値を保存します.右[ i ] = max(右［i + 1］、高さ［i］)

のような何かをしてください

現在、高さの配列をループし、効果的な高さとして効果的な高さを取る.トラップ水ユニットを追加します.

コード

int trap(vector<int>& height) {
        int N = height.size();

        vector<int> left(N, 0);
        vector<int> right(N, 0);

        left[0] = height[0];
        right[N - 1] = height[N - 1];

        for(int i = 1; i < N; i++){
            left[i] = max(left[i - 1], height[i]);
            right[N - i - 1] = max(height[N - i - 1], right[N - i]);
        }

        int ans = 0;

        for(int i = 0; i < N; i++){
            ans += min(left[i], right[i]) - height[i];
        }

        return ans;
    }

ハッピーコーディング!ディー
この記事はFOOLISH HUNGRYブログから取得されます.