最大矩形 图解题解

最大矩形这道题在问什么

给一个每格是 0 或 1 的矩阵，要框出一块全部由 1 组成的矩形，让面积最大。直接在二维里暴力枚举矩形，左右上下四条边随便组合就是 O(R²C²) 个候选，每个还要验证内部全 1，完全不可行。这题的价值就在于那一步降维转化。

为什么二维矩阵能压成柱状图

关键观察：任何一块全 1 矩形都有一条确定的底边，落在某一行上。反过来，固定「以第 r 行为底」之后，矩形在每一列能长多高，受限于该列从第 r 行向上连续 1 的个数——把这个数看成柱子的高度，第 r 行为底的所有全 1 矩形，恰好对应这排柱子构成的柱状图里的矩形。

于是原问题被拆成 R 个子问题：每一行作底生成一张柱状图，求柱状图最大矩形（这正是 LeetCode 84），所有行的答案取最大。因为每块矩形都有底行，逐行枚举不会漏掉任何候选。

heights 数组为什么遇 1 加一、遇 0 清零

heights[c] 的定义是：以当前行为底，第 c 列向上数连续 1 的个数。从上一行推到这一行只需一步增量更新：当前格是 1，柱子接着长高，heights[c] 加 1；当前格是 0，这一列被拦腰斩断，heights[c] 必须清零——0 上方那些 1 与本行不连通，不能参与以本行为底的矩形。清零这刀不砍，柱高虚高，答案就会把断开的区域误算进去。增量维护让每行的柱状图只花 O(C) 就能建好，不必每行都从头向上数。

每一行的柱状图怎么用单调栈结算

行内就是标准的 LeetCode 84 解法：维护柱高递增的栈（存下标），当前柱比栈顶矮时弹出栈顶结算——以它为高，宽度是当前下标与弹出后新栈顶之间的格数 i - left - 1，即左右两侧第一根更矮柱夹出的范围；末尾追加一根高 0 的哨兵柱，把扫完后还留在栈里的柱子全部逼出来结算。以题目的 4×5 示例矩阵为例，答案 6 出现在以第 2 行为底的柱状图 [3,1,3,2,2] 里：高 2、宽 3，覆盖第 2 到 4 列。

复杂度怎么算，哪些地方容易错

时间 O(R×C)：每行 O(C) 更新 heights 加 O(C) 单调栈（每根柱进出栈各一次），共 R 行。空间 O(C)：heights 数组与栈都只随列数增长，不需要二维辅助结构。

三个高频错误对应转化链上的三个环节：遇 0 不清零，柱状图本身就是错的；只算某一行、忘了对所有行取全局最大，而最大矩形的底行事先无从知晓；行内忘加末尾哨兵，栈里递增的尾巴没被结算，会漏掉答案。

Python

def maximalRectangle(matrix):
    if not matrix: return 0
    C = len(matrix[0])
    heights = [0] * C            # 逐行累加的柱高
    best = 0
    for row in matrix:
        for c in range(C):       # 遇 1 高度+1，遇 0 清零
            heights[c] = heights[c] + 1 if row[c] == "1" else 0
        best = max(best, largest(heights))   # LC84
    return best

def largest(hs):                 # 柱状图最大矩形·单调递增栈
    hs = hs + [0]; st = []; b = 0
    for i, h in enumerate(hs):
        while st and h < hs[st[-1]]:
            top = st.pop()
            left = st[-1] if st else -1
            b = max(b, hs[top] * (i - left - 1))
        st.append(i)
    return b

C++

int largest(vector<int> hs){            // 柱状图最大矩形
    hs.push_back(0); stack<int> st; int b = 0;
    for(int i = 0; i < (int)hs.size(); i++){
        while(!st.empty() && hs[i] < hs[st.top()]){
            int top = st.top(); st.pop();
            int left = st.empty() ? -1 : st.top();
            b = max(b, hs[top] * (i - left - 1));
        }
        st.push(i);
    }
    return b;
}
int maximalRectangle(vector<vector<char>>& m){
    if(m.empty()) return 0;
    int C = m[0].size(), best = 0;
    vector<int> heights(C, 0);
    for(auto& row : m){
        for(int c = 0; c < C; c++)
            heights[c] = row[c] == '1' ? heights[c] + 1 : 0;
        best = max(best, largest(heights));
    }
    return best;
}

Java

public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0) return 0;
    int C = matrix[0].length, best = 0;
    int[] heights = new int[C];                  // 逐行累加的柱高
    for (char[] row : matrix) {
        for (int c = 0; c < C; c++)              // 遇 1 高度+1，遇 0 清零
            heights[c] = row[c] == '1' ? heights[c] + 1 : 0;
        best = Math.max(best, largest(heights)); // LC84
    }
    return best;
}
private int largest(int[] hs) {                  // 柱状图最大矩形·单调栈
    int n = hs.length;
    int[] h = new int[n + 1];                    // 末尾哨兵 0
    System.arraycopy(hs, 0, h, 0, n);
    Deque<Integer> st = new ArrayDeque<>();
    int b = 0;
    for (int i = 0; i <= n; i++) {
        while (!st.isEmpty() && h[i] < h[st.peek()]) {
            int top = st.pop();
            int left = st.isEmpty() ? -1 : st.peek();
            b = Math.max(b, h[top] * (i - left - 1));
        }
        st.push(i);
    }
    return b;
}