LeetCode Maximal Rectangle：直方圖最大矩形面積的 DP 逐行遞推解法

題目大意

給定 0/1 矩陣，找全 1 子矩陣的最大面積。rows, cols ≤ 200。

核心轉化：逐行構建直方圖

對每一行，維護三個數組：

• height[j]：第 j 列連續 1 的高度（向上累加）。
• left[j]：以 j 為右邊界時，矩形能向左延伸的最遠列索引（含）。
• right[j]：以 j 為左邊界時，矩形能向右延伸的最遠列索引（含）。

第 i 行面積 = max_j (height[j] * (right[j] - left[j] + 1))。

遞推公式

掃描第 i 行：

int curLeft = 0, curRight = cols - 1;
// 更新 height & left
for (int j = 0; j < cols; ++j) {
    if (matrix[i][j] == '1') {
        height[j]++;
        left[j] = max(left[j], curLeft);
    } else {
        height[j] = 0; left[j] = 0; right[j] = cols - 1;
        curLeft = j + 1;
    }
}
// 更新 right（反向掃描）
for (int j = cols - 1; j >= 0; --j) {
    if (matrix[i][j] == '1') {
        right[j] = min(right[j], curRight);
        maxArea = max(maxArea, height[j] * (right[j] - left[j] + 1));
    } else {
        curRight = j - 1;
    }
}

Java 完整實現

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) return 0;
        int rows = matrix.length, cols = matrix[0].length;
        int[] height = new int[cols], left = new int[cols], right = new int[cols];
        Arrays.fill(right, cols - 1);
        int maxArea = 0;
        for (int i = 0; i < rows; ++i) {
            int curLeft = 0, curRight = cols - 1;
            for (int j = 0; j < cols; ++j) {
                if (matrix[i][j] == '1') {
                    height[j]++;
                    left[j] = Math.max(left[j], curLeft);
                } else {
                    height[j] = 0; left[j] = 0; right[j] = cols - 1;
                    curLeft = j + 1;
                }
            }
            for (int j = cols - 1; j >= 0; --j) {
                if (matrix[i][j] == '1') {
                    right[j] = Math.min(right[j], curRight);
                    maxArea = Math.max(maxArea, height[j] * (right[j] - left[j] + 1));
                } else {
                    curRight = j - 1;
                }
            }
        }
        return maxArea;
    }
}

複雜度

• 時間：O(rows × cols)，每格常數次操作。
• 空間：O(cols) 三個一維數組。

總結

LeetCode 85 是「二維最大子矩陣 → 一維直方圖最大矩形」的經典降維打擊。核心模板：逐行更新高度 + 雙向掃描維護左右邊界 + 面積計算。同模板解決 LeetCode 84（直方圖最大矩形）、HDU 1505 等問題。