Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

ヒストグラムの中の最大の長方形を見つけるアルゴリズム

https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/3/DPL_3_C

f:id:akiradeveloper529:20190307134332j:plain

ヒストグラムが与えられて、その中にある長方形の最大面積を求めるという問題は日常生活で気にすることはありませんが、競技プログラミングでは結構重要なアルゴリズムなのではないかと思いました。私は自力では思いつきませんでした。解法のアテ自体はつく人もいると思いますが、一発で正確に実装することは難しいと思うので、ライブラリ化しておくことにします。

考え方

長方形を作るというのはどういうことかというと、「ある時間iにa[i]を立てて、a[i]>a[j]となった時にa[i]*(j-i)」を面積として確定するということです。そうやって作っていった面積の最大値を求めましょうというのが問題です。

つまり、ヒストグラムを左から入れていって

  • 高さが増加していく
  • 減少した瞬間に面積を精算する

というデータ構造が実装出来ればよいです。

f:id:akiradeveloper529:20190210011842j:plain

コード

スタックを使って素直に表現します。i-new_iというのが、長方形の横幅に相当します。些細な最適化としては、h <= cur_hの部分を<に書き換えても動作します。なぜかというと、高さが同じであれば長方形を作れること以上の情報量はなく、結局、i-new_iで表現出来るからです。

もう1つのポイントは、ヒストグラムの末尾に高さ0のヒストグラムを衛兵として挿入することです。これによって、ヒストグラムが最後に全部消化されることが保証されます。これがないと例えば、ヒストグラムが常に単調増加してしまった場合に面積の計算が一切行われません。

fn max_area_in_histgram(hist: &[usize]) -> usize {
    let mut max_v = 0;

    let mut h = vec![];
    for &x in hist {
        h.push(x);
    }
    h.push(0); // sentinel

    let mut stack = vec![];

    for i in 0..h.len() {
        let cur_h = h[i];
        if stack.is_empty() {
            stack.push(Rect{h:cur_h,p:i});
        } else if stack.last().unwrap().h <= cur_h {
            stack.push(Rect{h:cur_h,p:i});
        } else if stack.last().unwrap().h > cur_h {
            let mut new_i = i;
            while !stack.is_empty() && stack.last().unwrap().h > cur_h {
                let rect = stack.pop().unwrap();
                new_i = rect.p;
                max_v = max(max_v, (i-new_i)*rect.h);
            }
            stack.push(Rect{h:cur_h,p:new_i})
        }
    }

    max_v
}

オーダーは、入力の長さNに対してO(N)です。

応用問題

実は一つ前の3_Bは、このアルゴリズムがあると簡単に解けます。前にあるということは他にも解き方があるのかも知れませんが、わかりませんでした。

https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/3/DPL_3_B

f:id:akiradeveloper529:20190210020613p:plain

これは、2次元配列dp[h][w]を用意して、dp[h]の値がちょうど自分から上を見た時のヒストグラムになるように予め計算して、h方向に全部計算していって最大値を探せばいいです。一行のオーダがO(W)なので、トータルでO(HW)となって間に合います。

あとは思いつきですが、重さのある荷物を逆順ソートする時の移動総重量を計算するとかも、アルゴリズムを少し修正すれば出来るかも知れないです。