class Solution {
public int maximalRectangle(char[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[] heights = new int[n];
int res = 0;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
if(matrix[i][j] == '1') heights[j]++;
else heights[j] = 0;
}
res = Math.max(res, largestRectangleArea(heights));
}
return res;
}
int largestRectangleArea(int[] heights) {
int len = heights.length + 2;
int[] newHeight = new int[len];
for(int i = 1; i < len - 1; i++) newHeight[i] = heights[i - 1];
Deque<Integer> stack = new ArrayDeque<>();
int res = 0;
for(int i = 0; i < len; i++){
while(!stack.isEmpty() && newHeight[i] < newHeight[stack.peek()]){
int pop = stack.pop();
int w = i - stack.peek() - 1;
int h = newHeight[pop];
int area = h * w;
res = Math.max(res, area);
}
stack.push(i);
}
return res;
}
}
85. 最大矩形
2023-12-10 03:58:01 38 阅读