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.lengthcols == matrix[0].length0 <= row, cols <= 200matrix[i][j]为'0'或'1'
注意：本题与主站 85 题相同（输入参数格式不同）： https://leetcode.cn/problems/maximal-rectangle/
解法
方法一：单调栈
把每一行视为柱状图的底部，对每一行求柱状图的最大面积即可。
时间复杂度 O ( m n ) O(mn) O(mn)，其中 m m m 表示 m a t r i x matrix matrix 的行数， n n n 表示 m a t r i x matrix matrix 的列数。
Python3
class Solution:
def maximalRectangle(self, matrix: List[str]) -> int:
if not matrix: return 0
n=len(matrix[0])
res=0
height_row=[0]*n
for row in matrix:
# 每行作为基座，累计向上的连续历史高度
for j,v in enumerate(row):
if v=="1":
height_row[j]+=1
else:
height_row[j]=0 #说明无基座，不需要累计，历史高度归于0
#
res=max(res,self.largestRectangleArea(height_row))
return res
def largestRectangleArea(self, heights: List[int]) -> int:
n=len(heights)
h_left_minid=[0]*n
h_right_minid=[n-1]*n
st=[]
for i,h in enumerate(heights):
while st and heights[st[-1]]>h:
idx=st.pop()
h_right_minid[idx]=i-1
st.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 + 1
st.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();
else
l[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 := 0
for _, 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 []int
left, 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]] = i
stk = 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.count
var heights = [Int](repeating: 0, count: n)
var ans = 0
for 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 = 0
let n = heights.count
var 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];
else
heights[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;
}
};