【C++】スタックを使ってヒストグラム内の最大長方形領域を効率的に求める方法

本記事では、C++を用いてヒストグラムの中から面積が最大となる長方形領域を見つけるプログラムを紹介します。この問題は、各バーの高さが与えられたヒストグラムにおいて、隣接するバーで構成できる最大の長方形の面積を求めるという、アルゴリズムの定番問題の一つです。

getArea()関数のアルゴリズム

このアルゴリズムはスタックを活用することで、時間計算量O(n)という高效な処理を実現しています。基本的な流れは以下の通りです。

1. 空のスタックを作成し、最大面積（largest_area）を0で初期化します。
2. 最初のバーから順に、すべてのバー hist[i]（i = 0 〜 n-1）について以下の処理を繰り返します。
3. スタックが空であるか、hist[i] がスタック顶部のバー以上の高さであれば、インデックス i をスタックにプッシュします。

逆に、現在のバーがスタック顶部のバーより小さい場合は、スタック顶部より高い要素がなくなるまでポップを続けます。その際、ポップしたバーを最小の高さとする長方形の面積を計算します。このとき、スタック内でポップした要素の一つ前が左端のインデックス、現在の位置 i が右端のインデックスとなります。

すべてのバーを走査した後、スタックに残っているバーがあれば、同様の手順でそれらをポップしながら、各バーを最小の高さとした場合の面積を計算し、最大値を更新していきます。

サンプルコード

#include<iostream>
#include<stack>
using namespace std;

int getArea(int hist[], int n)
{
    stack<int> st;
    int largest_area = 0;
    int top;
    int toparea;
    int i = 0;

    while (i < n)
    {
        // スタックが空、または現在のバーが顶部以上ならプッシュ
        if (st.empty() || hist[st.top()] <= hist[i])
            st.push(i++);
        else
        {
            // 現在のバーの方が低い場合、ポップして面積を計算
            top = st.top();
            st.pop();
            toparea = hist[top] * (st.empty() ? i :
                      i - st.top() - 1);
            if (largest_area < toparea)
                largest_area = toparea;
        }
    }

    // 残ったバーの面積を計算
    while (st.empty() == false)
    {
        top = st.top();
        st.pop();
        toparea = hist[top] * (st.empty() ? i :
                  i - st.top() - 1);
        if (largest_area < toparea)
            largest_area = toparea;
    }
    return largest_area;
}

int main()
{
    int hist[] = {6,7,4,5,3,2};
    int n = sizeof(hist)/sizeof(hist[0]);
    cout << "Largest area is " << getArea(hist, n);
    return 0;
}

実行結果

Largest area is 16

解説

この例では、高さ {6, 7, 4, 5, 3, 2} のヒストグラムに対して、最大面積 16 が得られます。これは高さ4のバーを中心に、幅4（インデックス0〜3）の長方形を形成した場合の面積（4 × 4 = 16）に相当します。

単純な全ペア比較による総当たり法ではO(n²)の計算量が必要ですが、スタックを用いることで各バーを一度ずつ処理するだけで済むため、大規模なデータに対しても高速に動作する点がこの手法の大きな利点です。