Maximal Rectangle（Python実装）| Row-wise Histogram + Monotonic Stack

アルゴリズム概要

各行を「底」として連続1の本数からなる 高さ配列（ヒストグラム） を更新し、行ごとに Largest Rectangle in Histogram（単調増加スタック）を適用して最大長方形面積を求めます。計算量は O(R·C)、追加メモリは O(C) です。

行の走査で高さ配列を1パス更新
スタックはインデックスのみ（push/pop）で単純高速
末尾は高さ0のセンチネルで確定処理を一括化

Flow (SVG, English labels)

ステップバイステップ解説（視覚化付き）

時間計算量

各行で O(C)、全体で O(R·C)。追加メモリは O(C)。

push/pop だけの単純なスタック操作
センチネル（j==cols）で終端処理を簡潔に
配列再利用で GC 負荷を抑制

Step 1 — Heights update (SVG)

Step 2 — Monotonic stack (SVG)

Step 3 — Update global maximum (SVG)

コード例（Python / LeetCode Class形式）

行番号・行ハイライト・コピー対応

from typing import List


class Solution:
    """
    LeetCode 85. Maximal Rectangle

    Competitive version:
    - Assumes matrix is a well-formed 2D list of '0'/'1' strings.
    - Time: O(R*C), Space: O(C)
    """

    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        rows: int = len(matrix)
        cols: int = len(matrix[0])
        if cols == 0:
            return 0

        # heights[j]: consecutive '1' height using current row as the base
        heights: List[int] = [0] * cols
        # stack will store indices; manual top pointer for perf
        stack: List[int] = [0] * (cols + 1)
        max_area: int = 0

        def largest_rectangle_in_histogram(h: List[int]) -> int:
            best: int = 0
            top: int = -1  # -1 means empty
            # sentinel: treat j==cols as height 0 to flush the stack
            for j in range(cols + 1):
                cur: int = 0 if j == cols else h[j]
                while top >= 0 and cur < h[stack[top]]:
                    height: int = h[stack[top]]
                    top -= 1
                    left_less: int = stack[top] if top >= 0 else -1
                    width: int = j - left_less - 1
                    area: int = height * width
                    if area > best:
                        best = area
                top += 1
                stack[top] = j
            return best

        for i in range(rows):
            row = matrix[i]
            # update heights
            for j in range(cols):
                heights[j] = heights[j] + 1 if row[j] == '1' else 0
            # compute area for this histogram
            area = largest_rectangle_in_histogram(heights)
            if area > max_area:
                max_area = area

        return max_area

    # Production-grade version with validations (optional)
    def maximalRectangle_production(self, matrix: List[List[str]]) -> int:
        if not isinstance(matrix, list):
            raise TypeError("matrix must be a list of lists")
        if not matrix:
            return 0
        cols: int = len(matrix[0])
        if cols == 0:
            return 0
        rows: int = len(matrix)
        if not (1 <= rows <= 200):
            raise ValueError("rows must be within [1, 200]")
        if not (1 <= cols <= 200):
            raise ValueError("cols must be within [1, 200]")
        for r, row in enumerate(matrix):
            if not isinstance(row, list) or len(row) != cols:
                raise ValueError("All rows must have identical length")
            for c, v in enumerate(row):
                if not isinstance(v, str) or (v != '0' and v != '1'):
                    raise TypeError("matrix[i][j] must be '0' or '1'")
        return self.maximalRectangle(matrix)

行番号・ハイライトは行高と同期済み。コピーは右上ボタン or 下のボタンから。

Page Top