LeetCode Maximal Rectangle：直方圖最大矩形面積的矩陣推廣

問題描述

給定一個僅包含 '0' 和 '1' 的二維字符矩陣，找出只包含 '1' 的最大矩形區域，返回其面積。

示例：

matrix = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
輸出: 6 (對應第 2-3 行、第 3-5 列的 2×3 矩形)

核心洞察：逐行轉化為直方圖問題

將矩陣每一行作為「底」，向上累積連續 '1' 的高度，形成直方圖。
第 i 行第 j 列的高度 h[j] = (matrix[i][j]=='1') ? h[j]+1 : 0。

然後對每一行的高度數組，求解 Largest Rectangle in Histogram (LeetCode 84)。所有行的最大值即為答案。

直方圖最大矩形：單調棧 O(n) 算法

維護遞增棧存儲索引。遇到較低高度時，彈出棧頂計算以該高度為高的最大矩形寬度。
哨兵技巧：在高度數組末尾追加 0，確保所有元素最終被彈出計算。

完整 Python 實現

class Solution:
    def maximalRectangle(self, matrix):
        if not matrix or not matrix[0]: return 0
        n = len(matrix[0])
        heights = [0] * (n + 1)  # 末尾哨兵 0
        max_area = 0
        for row in matrix:
            for i in range(n):
                heights[i] = heights[i] + 1 if row[i] == '1' else 0
            # 單調棧求最大矩形
            stack = [-1]
            for i in range(n + 1):
                while heights[i] < heights[stack[-1]]:
                    h = heights[stack.pop()]
                    w = i - stack[-1] - 1
                    max_area = max(max_area, h * w)
                stack.append(i)
        return max_area

C++ 實現

class Solution {
public:
    int maximalRectangle(vector>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return 0;
        int n = matrix[0].size();
        vector heights(n + 1, 0);
        int maxArea = 0;
        for (auto& row : matrix) {
            for (int i = 0; i < n; ++i)
                heights[i] = (row[i] == '1') ? heights[i] + 1 : 0;
            vector st = {-1};
            for (int i = 0; i <= n; ++i) {
                while (heights[i] < heights[st.back()]) {
                    int h = heights[st.back()]; st.pop_back();
                    int w = i - st.back() - 1;
                    maxArea = max(maxArea, h * w);
                }
                st.push_back(i);
            }
        }
        return maxArea;
    }
};

複雜度分析

• 時間：O(m·n)，m 行，每行 O(n) 單調棧。
• 空間：O(n)，高度數組 + 棧。

關鍵點總結

1. 降維打擊：二維矩陣問題 → 多次一維直方圖問題。
2. 動態高度更新：逐行掃描，O(1) 更新高度數組。
3. 單調棧：直方圖最大矩形的標準 O(n) 解法，必須熟練掌握。
4. 哨兵簡化邏輯：末尾加 0 統一處理剩餘棧內元素。

舉一反三

• LeetCode 84：Largest Rectangle in Histogram（本題核心子程序）
• LeetCode 221：Maximal Square（正方形版本，DP 解法）
• 最大子矩陣和、全 1 子矩陣計數等變體。