Pythonで解くヒストグラム内の最大長方形｜スタックによる効率的な解法

問題の概要

ヒストグラムの各棒の高さを表す整数配列が与えられたとします。各棒の幅はすべて1です。このとき、ヒストグラムの中に含まれる長方形のうち、面積が最大となるものを見つけるのがこの問題です。

解法のアプローチ：スタックを活用する

この問題はスタックを使うことで効率的に解けます。各棒について「その棒の高さを上限とした長方形」が左右にどこまで広げられるかを、インデックスをスタックで管理しながら求めていくのがポイントです。

アルゴリズムの手順

1. 空のスタックを作成し、i := 0、ans := 0 で初期化します。
2. i が heights のサイズ未満である間、以下を繰り返します。
   • スタックが空、またはスタック先頭要素の高さが heights[i] 以下の場合：
     i をスタックにプッシュし、i を1増やします。
   • それ以外の場合：
     
     • x := スタックの先頭要素を取り出す（ポップ）
     • height := heights[x]
     • スタックが空でなければ temp := height × (i − stack[-1] − 1)、空ならば temp := height × i
     • ans := ans と temp のうち大きい方
3. スタックが空になるまで、以下を繰り返します。
   • x := スタックの先頭要素
   • height := heights[x] を取得し、スタックから削除
   • スタックが空でなければ temp := height × (len(heights) − stack[-1] − 1)、空ならば temp := height × len(heights)
   • ans := ans と temp のうち大きい方
4. 最後に ans を返します。

Pythonでの実装例

以下のコードで実際の動作を確認できます。

class Solution(object):
    def largestRectangleArea(self, heights):
        stack = []
        i = 0
        ans = 0
        while i < len(heights):
            if len(stack) == 0 or heights[stack[-1]] <= heights[i]:
                stack.append(i)
                i += 1
            else:
                x = stack[-1]
                stack.pop()
                height = heights[x]
                temp = height * (i - stack[-1] - 1) if len(stack) != 0 else height * i
                ans = max(ans, temp)
        while len(stack) > 0:
            x = stack[-1]
            height = heights[x]
            stack.pop()
            temp = height * (len(heights) - stack[-1] - 1) if len(stack) != 0 else height * len(heights)
            ans = max(ans, temp)
        return ans

ob = Solution()
print(ob.largestRectangleArea([2, 1, 5, 7, 3, 2]))

入力

[2, 1, 5, 7, 3, 2]

出力

12

結果の解説

この入力の場合、高さ2以上の棒が6本連続して並んでいるため、「高さ2 × 幅6 = 12」となる長方形が最大面積になります。個々の高い棒（例えば高さ7）だけを見ると一見大きな面積に思えますが、幅との掛け合わせで全体を評価することが重要です。

計算量

• 時間計算量：O(n) — 各インデックスはスタックに最大1回プッシュされ、最大1回ポップされるためです。
• 空間計算量：O(n) — 高さが単調増加するような最悪ケースでは、すべてのインデックスがスタックに積まれます。