【Python】ヒストグラムの下に形成できる最大の長方形の面積を求めるプログラム

ヒストグラムの各棒の高さを表す数値のリストが与えられます。このとき、棒の下に形成できる最大の長方形の面積を求める問題を考えてみましょう。

例えば、入力が nums = [3, 2, 5, 7] の場合を見てみます。

この場合の出力は 10 になります。高さ2の棒が幅5にわたって連続しているため、2 × 5 = 10 が最大の面積となります。

解法のアプローチ：スタックを使った効率的なアルゴリズム

この問題は、単調増加スタックを利用することで O(n) の時間計算量で効率的に解けます。各棒について「その高さを維持できる最大の幅」を計算し、面積の最大値を更新していくのが基本の考え方です。

具体的な手順は以下の通りです。

1. スタックの初期化： 空のスタック stk を作成し、番兵（境界マーカー）として最初に -1 を挿入します。
2. 番兵の追加： heights の末尾に 0 を挿入します。これにより、ループの終了時に残っているすべての棒を強制的に処理できるようになります。
3. 答えの初期化： 変数 ans を 0 で初期化します。
4. 各棒の走査： i を 0 から heights のサイズまで繰り返し、以下を処理します。
   • heights[i] がスタックの先頭が指す高さより小さい間、次を繰り返します。
     • h := スタックの先頭が指す高さを取得し、スタックからポップする
     • w := i − スタックの新しい先頭 − 1（長方形の幅を計算）
     • ans := ans と (h × w) のうち大きい方を採用する
   • インデックス i をスタックにプッシュします。
5. 結果の返却： 最終的な ans を返します。

それでは、理解を深めるために実際の実装を見てみましょう。

実装例

class Solution:
    def solve(self, heights):
        stk = [-1]
        heights.append(0)
        ans = 0
        for i in range(len(heights)):
            while heights[i] < heights[stk[-1]]:
                h = heights[stk.pop()]
                w = i - stk[-1] - 1
                ans = max(ans, h * w)
            stk.append(i)
        return ans

ob = Solution()
nums = [3, 2, 5, 7]
print(ob.solve(nums))

入力

[3, 2, 5, 7]

出力

10

計算量について

このアルゴリズムでは、各インデックスはスタックに一度プッシュされ、一度だけポップされるため、時間計算量は O(n) です。また、使用しているのはスタックのみなので、空間計算量も O(n) に抑えられます。全組み合わせを総当たりで調べる O(n²) の素朴な手法と比べて、大規模な入力でも高速に動作する点が大きなメリットです。