Maximal Rectangle Algorithm

from typing import List

class Solution:
    """
    LeetCode 85. Maximal Rectangle
    競技プログラミング最適化版: O(R*C)時間、O(C)空間
    """

    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        """
        与えられた '0'/'1' 行列で、1のみから成る最大長方形の面積を返す。

        Args:
            matrix: R x C の2次元配列（各要素は '0' または '1'）

        Returns:
            最大長方形の面積（int）
        """
        if not matrix:
            return 0
        rows: int = len(matrix)
        cols: int = len(matrix[0])
        if cols == 0:
            return 0

        # heights[j]: 現在行を底とする列jの連続'1'の本数
        heights: List[int] = [0] * cols
        # 単調増加スタック（インデックスを格納）
        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  # スタックトップインデックス

            # j == cols でセンチネル（高さ0）として処理
            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_boundary: int = stack[top] if top >= 0 else -1
                    width: int = j - left_boundary - 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]
            # 高さ配列を更新
            for j in range(cols):
                heights[j] = heights[j] + 1 if row[j] == "1" else 0

            # 現在行を底とする最大長方形を計算
            area = largest_rectangle_in_histogram(heights)
            if area > max_area:
                max_area = area

        return max_area

def maximalRectangle_production(self, matrix: List[List[str]]) -> int:
    """
    業務開発向け: 包括的な入力検証を実施

    Raises:
        TypeError: 要素型が '0'/'1' 以外
        ValueError: 行長不揃い、サイズ範囲外など
    """
    # 入力検証
    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(f"Row {r} must have {cols} elements")
        for c, val in enumerate(row):
            if not isinstance(val, str) or val not in ("0", "1"):
                raise TypeError(f"matrix[{r}][{c}] must be '0' or '1'")

    # 検証通過後、高速版に委譲
    return self.maximalRectangle(matrix)