- dp+单调栈
对每一层维护本列中形成的最高值height,然后对每一层分别计算最大的矩形。
计算每一层最大矩形的时候,先用单调栈记录小于当前位置的左下标和右下标,矩形面积就是(right[i]-left[i]-1) * height[i]
class Solution {
public int maximalRectangle(char[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int h[] = new int[n], max = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(matrix[i][j] == '1') h[j]++;
else h[j] = 0;
}
max = Math.max(max, calc(h, n));
}
return max;
}
public int calc(int[] h, int n){
Deque<Integer> stk = new ArrayDeque<>();
int left[] = new int[n], right[] = new int[n];
Arrays.fill(right, n);
for(int i = 0; i < n; i++){
while(!stk.isEmpty() && h[stk.peek()] > h[i]) right[stk.pop()] = i;
left[i] = stk.isEmpty() ? -1 : stk.peek();
stk.push(i);
}
int res = 0;
for(int i = 0; i < n; i++){
res = Math.max(res, (right[i]-left[i]-1)*h[i]);
}
return res;
}
}
标签:right,最大,int,max,leetcode85,stk,++,矩形
From: https://www.cnblogs.com/xzh-yyds/p/16593301.html