読者です 読者をやめる 読者になる 読者になる

本履歴

購入した古本の履歴と時々プログラミング

Cracking the Code Interview 17.21 Volume Of Histogram

「世界で闘うプログラミング力を鍛える本」の最新版の翻訳が出たとのことで暇つぶしに眺めていたら面白い問題を見つけた。ヒストグラム地形が与えられるので雨が降った時に貯まる水の量を求めるというもの。例えば、3,1,5 という入力だと、3と5の間に高さ2の水たまりが出来るから2を出力すると言った具合。2,0,1,0,3だと5、基本0以上の数値が与えられる。 山頂を境として右と左に水たまりが出来ることは明らかだ。漢字の「山」という字の右左のくぼみに水が貯まるイメージ。つまり、左から山頂までの水たまりの体積が分かったら、今度は右から同じことをすればOK。従って、まず山頂を求め、そこで左右に分割し、右は反転し、vol_of_slopeメソッドにあとは計算を任せる。vol_of_slopeは一番最後に最高峰の壁が出てくることになっているので、配列を読みながら逐次現在までの最高点の更新と、最高点以下の地形が出てきたらその差分が水で埋まるので加えていく。

def volume_of_histgram(a)
    max_hight = max_idx = 0
    a.each_with_index{|h, idx|
        if h > max_hight
            max_hight = h
            max_idx = idx
        end
    }
    vol_of_slope(a[0..max_idx]) + vol_of_slope(a[max_idx..-1].reverse)
end

#the rightmost must be the highest
def vol_of_slope(a)
    ret = 0
    prev_highest = 0
    a.each{|h|
        if h > prev_highest
            prev_highest = h
        elsif h < prev_highest
            ret += prev_highest - h
        end
    }
    ret
end