Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 6.
一刷
题解：
解题思路
根据上图，可以清楚的看出本题可以转化为Largest Rectangle in Histogarm来做
初始化height = [0, 0 ,0 ....]
对于每一行，先求出以这一行为x轴的每个柱子的高度，求解时，可以每次基于上一行的值进行更新。然后O(n)的时间求出最大矩形，不断更新全局变量res
时间复杂度为 O(n * (n + n)) = O(n2)
public class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix == null || matrix.length == 0) return 0;
int colNum = matrix[0].length;
int[] accumulatedHeights = new int[colNum];
int max = 0;
for(char[] row : matrix){
for(int i=0; i<colNum; i++){
//the accumulated, consecutive number of 1
accumulatedHeights[i] = row[i] == '0' ? 0 : accumulatedHeights[i] + 1;
}
max = Math.max(calcLargestHist(accumulatedHeights), max);
}
return max;
}
private int calcLargestHist(int[] heights){
if(heights == null || heights.length == 0) return 0;
Stack<Integer> stack = new Stack<Integer>();//store the index
int max = 0;
for(int i=0; i<=heights.length; i++){
int curt = (i == heights.length)? -1: heights[i];//guaranteen the stack is ascending
while(!stack.isEmpty() && curt<=heights[stack.peek()]){
int h = heights[stack.pop()];
int w = stack.isEmpty()? i: i - stack.peek() - 1;
max = Math.max(max, h*w);
}
stack.push(i);
}
return max;
}
}
