Source: Dev.to

初学者友好的指南：最大矩形（LeetCode 85）—— C、Python、JavaScript

题目描述

给定一个仅包含 '0' 和 '1' 的二维二进制矩阵，找出只包含 '1' 的最大矩形，并返回其面积。

示例 1
输入：

[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]

输出：6

示例 2
输入：[["0"]]
输出：0

---

思路概述

1. 把每一行看成直方图

   • 对于第 i 行的每一列 j，统计从第 i 行向上连续出现 '1' 的个数，记为 height[j]。
   • 这样第 i 行就对应了一组柱状图的高度。

2. 在每一行的直方图上求最大矩形面积

   • 这一步可以使用「单调栈」的经典算法（与 LeetCode 84 “柱状图中最大的矩形”相同）。
   • 通过一次遍历即可得到该行对应的最大矩形面积。

3. 遍历所有行，取全局最大值

时间复杂度：O(m * n)（m 为行数，n 为列数）
空间复杂度：O(n)（用于存储 height 数组和栈）

---

代码实现

下面分别给出 C、Python、JavaScript 三种语言的实现。代码块内部的代码保持原样，不进行翻译。

C 语言实现

int maximalRectangle(char** matrix, int matrixSize, int* matrixColSize){
    if (matrixSize == 0) return 0;
    int n = matrixColSize[0];
    int *height = (int *)calloc(n, sizeof(int));
    int maxArea = 0;

    for (int i = 0; i < matrixSize; ++i) {
        // 更新 height 数组
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == '1')
                height[j] += 1;
            else
                height[j] = 0;
        }
        // 在当前直方图上求最大矩形
        maxArea = fmax(maxArea, largestRectangleArea(height, n));
    }
    free(height);
    return maxArea;
}

Python 实现

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        n = len(matrix[0])
        height = [0] * n
        max_area = 0

        for row in matrix:
            # 更新 height
            for i in range(n):
                height[i] = height[i] + 1 if row[i] == '1' else 0
            # 计算当前直方图的最大矩形
            max_area = max(max_area, self.largestRectangleArea(height))
        return max_area

    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = []
        max_area = 0
        heights.append(0)  # 哨兵
        for i, h in enumerate(heights):
            while stack and heights[stack[-1]] > h:
                height = heights[stack.pop()]
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)
        heights.pop()  # 移除哨兵
        return max_area

JavaScript 实现

var maximalRectangle = function(matrix) {
    if (matrix.length === 0) return 0;
    const n = matrix[0].length;
    const height = new Array(n).fill(0);
    let maxArea = 0;

    for (const row of matrix) {
        // 更新 height
        for (let i = 0; i < n; i++) {
            height[i] = row[i] === '1' ? height[i] + 1 : 0;
        }
        // 计算当前直方图的最大矩形
        maxArea = Math.max(maxArea, largestRectangleArea(height));
    }
    return maxArea;
};

function largestRectangleArea(heights) {
    const stack = [];
    let maxArea = 0;
    heights.push(0); // 哨兵
    for (let i = 0; i < heights.length; i++) {
        while (stack.length && heights[stack[stack.length - 1]] > heights[i]) {
            const h = heights[stack.pop()];
            const w = stack.length ? i - stack[stack.length - 1] - 1 : i;
            maxArea = Math.max(maxArea, h * w);
        }
        stack.push(i);
    }
    heights.pop(); // 移除哨兵
    return maxArea;
}

---

复杂度分析

• 时间复杂度：我们遍历每一行，每行内部遍历每一列一次，且单调栈的操作均为 O(n)，因此总体为 O(m·n)。
• 空间复杂度：主要是 height 数组和栈，均与列数 n 成线性关系。

---

小结

• 将二维矩阵转化为每行的直方图是解决本题的关键思路。
• 通过单调栈在每行的直方图上求最大矩形，可在 O(n) 时间内完成。
• 该方法在实际面试中常被考察，掌握后即可轻松应对 LeetCode 85 以及类似的二维几何问题。

祝你刷题顺利，继续加油！

问题概述

给定

• 一个由字符 '0' 和 '1' 组成的二维二进制 matrix。

目标

• 找到只包含 '1' 的最大矩形，并返回其面积。

示例

Input:  matrix = [
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6
Explanation: 最大矩形如上图所示。

直觉

直接检查每一个可能的矩形是不可行的。
相反，把每一行当作 地面，并计算它上方连续 '1' 的高度。
这样每一行就变成了一个 直方图。

如果我们能在直方图中找到最大的矩形，就可以对每一行重复这个过程。
单调栈 能在一次线性遍历中提供所需的信息：

对于下标为 i 的柱子：

width  = NSE[i] - PSE[i] - 1
area   = heights[i] * width

所有行的最大面积即为答案。

代码块

C++ 解法

class Solution {
public:
    int maximalRectangle(vector>& matrix) {
        if (matrix.empty()) return 0;
        int n = matrix.size(), m = matrix[0].size();

        vector heights(m, 0), pse(m), nse(m);
        stack ps, ns;
        int max_area = 0;

        for (int i = 0; i  heights[j]) {
                    nse[ns.top()] = j;
                    ns.pop();
                }
                ns.push(j);

                while (!ps.empty() && heights[ps.top()] >= heights[j]) {
                    ps.pop();
                }
                pse[j] = (ps.empty() ? -1 : ps.top());
                ps.push(j);
            }

            // Update max area for this histogram
            for (int j = 0; j  int:
        if not matrix:
            return 0

Python（部分片段）

int:
    if not matrix:
        return 0

Python 解法

def maximalRectangle(matrix):
    if not matrix:
        return 0

    rows, cols = len(matrix), len(matrix[0])
    heights = [0] * cols
    max_area = 0

    for i in range(rows):
        # Update heights based on the current row
        for j in range(cols):
            heights[j] = heights[j] + 1 if matrix[i][j] == '1' else 0

        # Largest Rectangle in Histogram for this row
        stack = []
        pse = [-1] * cols
        nse = [cols] * cols

        # Next Smaller Element
        for j in range(cols):
            while stack and heights[stack[-1]] > heights[j]:
                nse[stack.pop()] = j
            stack.append(j)

        # Previous Smaller Element (backwards pass)
        stack.clear()
        for j in range(cols - 1, -1, -1):
            while stack and heights[stack[-1]] > heights[j]:
                pse[stack.pop()] = j
            stack.append(j)

        # Compute area for each bar
        for j in range(cols):
            area = heights[j] * (nse[j] - pse[j] - 1)
            max_area = max(max_area, area)

    return max_area

JavaScript 解法（版本 1）

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalRectangle = function(matrix) {
    if (matrix.length === 0) return 0;

    const rows = matrix.length;
    const cols = matrix[0].length;
    const heights = new Array(cols).fill(0);
    let maxArea = 0;

    for (let i = 0; i  heights[j]) {
                nse[stack.pop()] = j;
            }
            stack.push(j);
        }

        // Previous Smaller Element (reverse pass)
        stack.length = 0; // clear stack
        for (let j = cols - 1; j >= 0; --j) {
            while (stack.length && heights[stack[stack.length - 1]] > heights[j]) {
                pse[stack.pop()] = j;
            }
            stack.push(j);
        }

        // Compute area for each bar
        for (let j = 0; j  heights[j]) {
                nse[stack.pop()] = j;
            }
            stack.push(j);
        }

        // Reset stack for PSE
        stack.length = 0;
        for (let j = cols - 1; j >= 0; j--) {
            while (stack.length && heights[stack[stack.length - 1]] > heights[j]) {
                pse[stack.pop()] = j;
            }
            stack.push(j);
        }

        // Compute max area for this row
        for (let j = 0; j < cols; j++) {
            maxArea = Math.max(maxArea, heights[j] * (nse[j] - pse[j] - 1));
        }
    }

    return maxArea;
}

JavaScript 解法（版本 2）

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalRectangle = function(matrix) {
    if (matrix.length === 0) return 0;

    const rows = matrix.length;
    const cols = matrix[0].length;
    const heights = new Array(cols).fill(0);
    let maxArea = 0;

    for (let i = 0; i < rows; ++i) {
        // Update heights
        for (let j = 0; j < cols; ++j) {
            heights[j] = matrix[i][j] === '1' ? heights[j] + 1 : 0;
        }

        // Compute NSE
        const nse = new Array(cols).fill(cols);

        const stack = [];
        for (let j = 0; j < cols; ++j) {
            while (stack.length && heights[stack[stack.length - 1]] > heights[j]) {
                nse[stack.pop()] = j;
            }
            stack.push(j);
        }

        // Compute PSE
        const pse = new Array(cols).fill(-1);
        stack.length = 0;
        for (let j = cols - 1; j >= 0; --j) {
            while (stack.length && heights[stack[stack.length - 1]] > heights[j]) {
                pse[stack.pop()] = j;
            }
            stack.push(j);
        }

        // Calculate max area for this row
        for (let j = 0; j < cols; ++j) {
            maxArea = Math.max(maxArea, heights[j] * (nse[j] - pse[j] - 1));
        }
    }

    return maxArea;
}

关键要点

• 问题简化： 将二维问题视为一系列一维问题（直方图）的思维方式非常强大。
• 单调栈： 在 O(n) 时间内寻找“最近的更小”或“最近的更大”元素时，这些栈是必不可少的。
• 空间‑时间权衡： 通过为高度和栈使用 O(n) 的额外空间，我们实现了 O(m × n) 的总体时间复杂度，远快于暴力方法。

最后思考

这个问题是高级技术面试中的常见题目，因为它结合了多层逻辑。在实际工程中，这些技术被用于：

• Computer Vision – 用于目标检测。
• Database Optimization – 用于查找连续的空闲空间块。
• UI Rendering – 用于布局引擎。

掌握单调栈将使你成为更强大的问题解决者。