方法 算法思想:单调栈 时间复杂度: 空间复杂度: 边界条件: 补充知识:
class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix.length==0) return 0;
int []heights=new int[matrix[0].length]; //获取列
int maxArea=0;
for(int row=0;row<matrix.length;row++){ //行列
for(int col=0;col<matrix[0].length;col++){
if(matrix[row][col]=='1') heights[col]+=1; //列
else heights[col]=0; //直接赋值为0?
}
maxArea = Math.max(maxArea, largestRectangleArea(heights)); //这一行的最大面积
}
return maxArea;
}
public int largestRectangleArea(int[] heights) {
int len = heights.length;
if (len == 0) {
return 0;
}
if (len == 1) {
return heights[0];
}
int res = 0;
int[] newHeights = new int[len + 2];
newHeights[0] = 0;
System.arraycopy(heights, 0, newHeights, 1, len);
newHeights[len + 1] = 0;
len += 2;
heights = newHeights;
Deque<Integer> stack = new ArrayDeque<>(len);
// 先放入哨兵,在循环里就不用做非空判断
stack.addLast(0);
for (int i = 1; i < len; i++) {
while (heights[i] < heights[stack.peekLast()]) {
int curHeight = heights[stack.pollLast()];
int curWidth = i - stack.peekLast() - 1;
res = Math.max(res, curHeight * curWidth);
}
stack.addLast(i);
}
return res;
}
}