LeetCode85 最大矩形
题目描述
给定一个仅包含 0
和 1
、大小为 rows x cols
的二维二进制矩阵,找出只包含 1
的最大矩形,并返回其面积。
样例
输入:matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出:6
解释:最大矩形如上图所示。
输入:matrix = []
输出:0
输入:matrix = [["0"]]
输出:0
输入:matrix = [["1"]]
输出:1
输入:matrix = [["0","0"]]
输出:0
算法分析
- 枚举每一行
- 每一行初始化高度
- 若当前位置是0,则h[i,j] = 0
若当前位置是1,则h[i,j] = 1 + h[i,j]
- 若当前位置是0,则h[i,j] = 0
- 按照84题单调栈的做法
- 找到左边第一个比他小的、右边第一个比它小的
- (r[i] - l[i] - 1)*h[i]
时间复杂度
$O(n^{2})$
Java代码
class Solution {
static int largestRectangleArea(int[] h){
int n = h.length;
Stack<Integer> stk = new Stack<Integer>();
int[] left = new int[n];
int[] right = new int[n];
for(int i = 0; i < n; i ++){
while(!stk.isEmpty() && h[stk.peek()] >= h[i]) stk.pop();
if(stk.isEmpty()) left[i] = -1;
else left[i] = stk.peek();
stk.push(i);
}
stk.clear();
//初始化右边数组
for(int i = n-1; i >= 0; i --){
while(!stk.isEmpty() && h[stk.peek()] >= h[i]) stk.pop();
if(stk.isEmpty()) right[i] = n;
else right[i] = stk.peek();
stk.push(i);
}
int res = 0;
for(int i = 0; i < n; i ++){
res = Math.max(res, h[i] * (right[i] - left[i] - 1));
}
return res;
}
public int maximalRectangle(char[][] matrix) {
if(matrix.length <= 0 || matrix[0].length < 0) return 0;
int n = matrix.length;
int m = matrix[0].length;
int[][] h = new int[n+10][m+10];
for(int i = 0; i < n; i ++){
for(int j = 0; j < m; j ++){
if(matrix[i][j] == '1'){
if(i == 0){
h[i][j] = 1;
}else{
h[i][j] = h[i-1][j] + 1;
}
}
}
}
int res = 0;
for(int i = 0; i < n; i ++){
res = Math.max(res, largestRectangleArea(h[i]));
}
return res;
}
}