LeetCode 解答 #41. First Missing Positive プログラミング練習

問題：

難易度:　hard
入力:　int 型array[]
目的: 入力数字を壁の高さとして、雨が降った時最大で何ユニット分の水が汲めるか
出力:　int

入力された数字はそれぞれが壁の高さを表しています。
壁の位置はindexと同等、1番目と2番目の数字の間に1ユニット空いているイメージです。
上の例を見てもらえばわかりやすいと思うのですが、
黒い部分が壁で、青い部分が最大の水たまりです。
水の高さは両端の一番低い壁の高さに依存します。

注意すべき事:　

• 入力すべて非負数である

以下回答です。

class Solution {
    public int trap(int[] height) {
        int res = 0;
        int rightmax = 0;
        int leftmax = 0;
        int l = 0, r = height.length-1; 
        while (l <= r) {
            rightmax = Math.max(rightmax, height[r]);
            leftmax = Math.max(leftmax, height[l]);
            if (leftmax < rightmax) {
                res += leftmax - height[l];
                l++;
            } else {
                res += rightmax - height[r];
                r--;
            }
        }
        return res;
    }
}

普通に左端から低い壁を探し足していくやり方でもAcceptはもらえますが、
賢い方法をネットで見つけたので↑に書かせてもらいました。
全体を一つの容器として考えた方法です。
まず、左端と右端両サイドから同時に見ていきます。
低い方から中心に向かって進みます。溜められる水の量は低い壁に依存するからです。
leftmax と rightmaxは現時点で相対的に高い壁を記録しています。
低い方から溜められる水を足していきます。
少し想像しにくいかもしれませんが、一本の一番高い壁があったとして、
汲める水の量はそれに依存しないので片方はそこで止まります。
別サイドの一番高い壁によって水の量が決まるので反対側の一番高い壁を記録しその差を足していくイメージです。

今日は以上。
よいプログラミング生活を！