---
title: "最大矩形"
created: 2025-11-28
tags:
  - 算法
---

# 最大矩形

## 题目  [Maximal Rectangle](https://leetcode.com/problems/maximal-rectangle/description/)

![[image-78cba831.png]]

## 思路分析

![[image-41d77469.png]]

将二维矩阵拆分成一行一行

问题转换为 [[直方图中最大的矩形|直方图中最大的矩形]]

在这里用数组模拟 N不能在编译时确定

所以要用到new操作 所以反倒是比直接stl vector慢

## 代码实现

**模拟单调栈 33ms**

```java
class Solution {
public:
    // 计算直方图中最大矩形的面积
    int histMaximalRectangle(const vector<int>& heights) {
        int n = heights.size();

        int* h = new int[n + 2];// 动态数组以容纳哨兵值
        h[0] = -1;
        h[n + 1] = -1;
        for (int i = 0; i < n; ++i) {
            h[i + 1] = heights[i];
        }
        int* l = new int[n + 2];
        int* r = new int[n + 2];
        int* s = new int[n + 2];

        int top = 0;
        s[0]=0;
        for(int i=1;i<=n;i++){
            while(h[s[top]]>=h[i])
                top--;
            l[i]=s[top];
            s[++top]=i;
        }

        top=0;
        s[0]=n+1;
        for(int i=n;i>=1;i--){
            while(h[s[top]]>=h[i])
                top--;
            r[i]=s[top];
            s[++top]=i;
        }

        int max_area = 0;
        for (int i = 1; i <= n; ++i) {
            max_area = max(max_area, h[i] * ((r[i]-1)-(l[i]+1)+1));
        }

        delete[] h;
        delete[] l;
        delete[] r;
        delete[] s;

        return max_area;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        // 检查矩阵是否为空
        if (matrix.empty())
            return 0;
        int rowN = matrix.size();// 矩阵的行数
        int colN = matrix[0].size();// 矩阵的列数
        // 如果行数或列数为0，则返回0
        if (rowN == 0 || colN == 0)
            return 0;

        // 存储每行的直方图
        vector<vector<int>> hist_matrix(rowN, vector<int>(colN, 0));
        int max_area = 0;// 最大面积

        // 构建每一行的直方图
        for (int i = 0; i < rowN; ++i) {
            for (int j = 0; j < colN; ++j) {
                if (matrix[i][j] == '1') {
                    hist_matrix[i][j] = 1;// 当前元素为'1'
                    if (i - 1 >= 0) {// 如果不是第一行，累加上方的值
                        hist_matrix[i][j] += hist_matrix[i-1][j];
                    }
                }
            }
        }
        for (int i = 0; i < rowN; ++i) {
            max_area = max(max_area, histMaximalRectangle(hist_matrix[i]));
        }
        return max_area;
    }
};
```

**stl 27ms**

```java
class Solution {
public:
    // 计算直方图中最大矩形的面积
    int histMaximalRectangle(const vector<vector<int>>& matrix, int row_idx) {
         stack<int> stack; // 用于存储索引的栈
        int max_area = 0; // 最大面积
        vector<int> row = matrix[row_idx]; // 当前行的直方图
        row.push_back(0); // 添加哨兵以简化处理

        for (int i = 0; i < row.size(); ++i) {
            int curr = row[i];
            // 当栈非空且当前元素小于栈顶元素对应的高度时
            while (!stack.empty() && row[stack.top()] > curr) {
                int top = stack.top(); // 获取栈顶元素
                stack.pop(); // 弹出栈顶元素
                int left = stack.empty() ? 0 : stack.top() + 1; // 计算左边界
                int right = i - 1; // 计算右边界
                // 更新最大面积
                max_area = max(max_area, (right - left + 1) * row[top]);
            }
            stack.push(i); // 将当前索引压入栈
        }

        return max_area; // 返回最大面积
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        // 检查矩阵是否为空
        if (matrix.empty())
            return 0;
        int rowN = matrix.size();// 矩阵的行数
        int colN = matrix[0].size();// 矩阵的列数
        // 如果行数或列数为0，则返回0
        if (rowN == 0 || colN == 0)
            return 0;

        // 存储每行的直方图
        vector<vector<int>> hist_matrix(rowN, vector<int>(colN, 0));
        int max_area = 0;// 最大面积

        // 构建每一行的直方图
        for (int i = 0; i < rowN; ++i) {
            for (int j = 0; j < colN; ++j) {
                if (matrix[i][j] == '1') {
                    hist_matrix[i][j] = 1;// 当前元素为'1'
                    if (i - 1 >= 0) {// 如果不是第一行，累加上方的值
                        hist_matrix[i][j] += hist_matrix[i-1][j];
                    }
                }
            }
            // 计算当前行直方图中最大的矩形面积
            int row_max_area = histMaximalRectangle(hist_matrix, i);
            // 更新全局最大面积
            max_area = max(row_max_area, max_area);
        }

        return max_area;
    }
};
```

## 同类题型

## 视频讲解


---
⬅️ [[2-Learning/02-算法/03-刷题理模型/栈与队列相关模型/单调栈/接雨水|接雨水]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/栈与队列相关模型/单调栈/最长连续子序列|最长连续子序列]]