---

comments: true
edit_url: https://github.com/doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20040.%20%E7%9F%A9%E9%98%B5%E4%B8%AD%E6%9C%80%E5%A4%A7%E7%9A%84%E7%9F%A9%E5%BD%A2/README.md

剑指 Offer II 040. 矩阵中最大的矩形

题目描述

给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。

注意：此题 matrix 输入格式为一维 01 字符串数组。

 

示例 1：

输入：matrix = ["10100","10111","11111","10010"]
输出：6
解释：最大矩形如上图所示。

示例 2：

输入：matrix = []
输出：0

示例 3：

输入：matrix = ["0"]
输出：0

示例 4：

输入：matrix = ["1"]
输出：1

示例 5：

输入：matrix = ["00"]
输出：0

 

提示：

• rows == matrix.length
• cols == matrix[0].length
• 0 <= row, cols <= 200
• matrix[i][j] 为 '0' 或 '1'

 

注意：本题与主站 85 题相同（输入参数格式不同）： https://leetcode.cn/problems/maximal-rectangle/

解法

方法一：单调栈

把每一行视为柱状图的底部，对每一行求柱状图的最大面积即可。

时间复杂度 $O(mn)$，其中 $m$ 表示 $matrix$ 的行数，$n$ 表示 $matrix$ 的列数。

Python3

class Solution:def maximalRectangle(self, matrix: List[str]) -> int:if not matrix: return 0n=len(matrix[0])res=0height_row=[0]*nfor row in matrix:# 每行作为基座，累计向上的连续历史高度for j,v in enumerate(row):if v=="1":height_row[j]+=1else:height_row[j]=0 #说明无基座，不需要累计，历史高度归于0#res=max(res,self.largestRectangleArea(height_row))return resdef largestRectangleArea(self, heights: List[int]) -> int:n=len(heights)h_left_minid=[0]*nh_right_minid=[n-1]*nst=[]for i,h in enumerate(heights):while st and heights[st[-1]]>h:idx=st.pop()h_right_minid[idx]=i-1st.append(i)heights_copy=heights[::-1]st = []for i, h in enumerate(heights_copy):while st and heights_copy[st[-1]] > h:idx = st.pop()h_left_minid[n-1-idx] = n-1-i + 1st.append(i)return max((r-l+1)*h for h,r,l in zip(heights,h_right_minid,h_left_minid))

Java

class Solution {public int maximalRectangle(String[] matrix) {if (matrix == null || matrix.length == 0) {return 0;}int n = matrix[0].length();int[] heights = new int[n];int ans = 0;for (var row : matrix) {for (int j = 0; j < n; ++j) {if (row.charAt(j) == '1') {heights[j] += 1;} else {heights[j] = 0;}}ans = Math.max(ans, largestRectangleArea(heights));}return ans;}private int largestRectangleArea(int[] heights) {int res = 0, n = heights.length;Deque<Integer> stk = new ArrayDeque<>();int[] left = new int[n];int[] right = new int[n];Arrays.fill(right, n);for (int i = 0; i < n; ++i) {while (!stk.isEmpty() && heights[stk.peek()] >= heights[i]) {right[stk.pop()] = i;}left[i] = stk.isEmpty() ? -1 : stk.peek();stk.push(i);}for (int i = 0; i < n; ++i) {res = Math.max(res, heights[i] * (right[i] - left[i] - 1));}return res;}
}

C++

class Solution {
public:int h[210];int l[210], r[210];int maximalRectangle(vector<string>& matrix) {int n = matrix.size();if (n == 0) return 0;int m = matrix[0].size();int ans = 0;stack<int> st;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {h[j] = (matrix[i][j] == '1' ? h[j] + 1 : 0);while (st.size() && h[j] <= h[st.top()]) {ans = max(ans, (j - l[st.top()] - 1) * h[st.top()]);st.pop();}if (st.size())l[j] = st.top();elsel[j] = -1;st.push(j);}while (st.size()) {ans = max(ans, (m - 1 - l[st.top()]) * h[st.top()]);st.pop();}}return ans;}
};

Go

func maximalRectangle(matrix []string) int {if len(matrix) == 0 {return 0}n := len(matrix[0])heights := make([]int, n)ans := 0for _, row := range matrix {for j, v := range row {if v == '1' {heights[j]++} else {heights[j] = 0}}ans = max(ans, largestRectangleArea(heights))}return ans
}func largestRectangleArea(heights []int) int {res, n := 0, len(heights)var stk []intleft, right := make([]int, n), make([]int, n)for i := range right {right[i] = n}for i, h := range heights {for len(stk) > 0 && heights[stk[len(stk)-1]] >= h {right[stk[len(stk)-1]] = istk = stk[:len(stk)-1]}if len(stk) > 0 {left[i] = stk[len(stk)-1]} else {left[i] = -1}stk = append(stk, i)}for i, h := range heights {res = max(res, h*(right[i]-left[i]-1))}return res
}

Swift

class Solution {func maximalRectangle(_ matrix: [String]) -> Int {guard let firstRow = matrix.first else {return 0}let n = firstRow.countvar heights = [Int](repeating: 0, count: n)var ans = 0for row in matrix {for (j, char) in row.enumerated() {if char == "1" {heights[j] += 1} else {heights[j] = 0}}ans = max(ans, largestRectangleArea(heights))}return ans}private func largestRectangleArea(_ heights: [Int]) -> Int {var res = 0let n = heights.countvar stack = [Int]()var left = [Int](repeating: -1, count: n)var right = [Int](repeating: n, count: n)for i in 0..<n {while !stack.isEmpty && heights[stack.last!] >= heights[i] {right[stack.removeLast()] = i}left[i] = stack.isEmpty ? -1 : stack.last!stack.append(i)}for i in 0..<n {res = max(res, heights[i] * (right[i] - left[i] - 1))}return res}
}

方法二

C++

class Solution {
public:int maximalRectangle(vector<string>& matrix) {if (matrix.empty()) return 0;int n = matrix[0].size();vector<int> heights(n);int ans = 0;for (auto& row : matrix) {for (int j = 0; j < n; ++j) {if (row[j] == '1')++heights[j];elseheights[j] = 0;}ans = max(ans, largestRectangleArea(heights));}return ans;}int largestRectangleArea(vector<int>& heights) {int res = 0, n = heights.size();stack<int> stk;vector<int> left(n, -1);vector<int> right(n, n);for (int i = 0; i < n; ++i) {while (!stk.empty() && heights[stk.top()] >= heights[i]) {right[stk.top()] = i;stk.pop();}if (!stk.empty()) left[i] = stk.top();stk.push(i);}for (int i = 0; i < n; ++i)res = max(res, heights[i] * (right[i] - left[i] - 1));return res;}
};