Largest Rectangle in Histogram — Python 技術解説

対象アルゴリズム：単調増加スタック法 (Monotonic Increasing Stack) ／言語：Python (CPython 3.11+)

Time O(n) Space O(n) LeetCode Class カラーパレット最適化レスポンシブ

1. アルゴリズム概要

配列を一次走査し、高さが単調に増加するインデックスをスタックへ保持します。現在の高さがスタック頂点より低くなった時、頂点を最小高さとする長方形の幅が確定します。末尾では番兵（高さ0）を用い、残りを一括処理することで1本のループで実装できます。

対象配列（例）

[2, 1, 5, 6, 2, 3]

最大面積（進行中）

現在の i / n

0 / 6

2. コード例（シンタックスハイライト付き）

Python / LeetCode Class

行番号コピー可

from typing import List

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n: int = len(heights)
        stack: List[int] = []
        h = heights
        ma = 0
        st = stack

        for i in range(n + 1):
            curr: int = 0 if i == n else h[i]  # sentinel at i==n
            while st and curr < h[st[-1]]:
                top: int = st.pop()
                height: int = h[top]
                left: int = st[-1] if st else -1
                width: int = i - left - 1
                area: int = height * width
                if area > ma:
                    ma = area
            st.append(i)  # push current index (sentinel allowed)
        return ma

※ 余白を圧縮し、行番号ガターを狭めて空白を最小化しています。

3. ステップバイステップ解説

例：[2, 1, 5, 6, 2, 3] を順に処理。各ステップでスタックと更新面積を表示します（クリックでジャンプ）。

4. 視覚的図解・フローチャート

Step 1 / 7

現在バースタック中 pop対象

5. 時間計算量の説明

時間計算量： O(n) — 各インデックスは高々 1 回 push / 1 回 pop。
空間計算量： O(n) — スタックに最大 n 個のインデックスを保持。