Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
思路：此题的意思是给一个为0或1的矩阵，求所有为1组成的最大矩阵的面积。
此题能够巧妙转化为求最大直方图面积的问题。
public class Solution {
//其思想是将每一列的1逐行相加，遇0为0。遇1相加
//然后转化为求每一行的最大直方图面积的求解
//最后求出最大全为1的矩形面积
public int maximalRectangle(char[][] matrix) {
//边界条件
if(matrix.length == 0 || matrix[0].length == 0){
return 0;
}
/**
* 按列将每列的1逐行相加
*/
for(int j = 0; j < matrix[0].length; j++){
for(int i = 1; i < matrix.length; i++){
if(matrix[i][j] != '0'){//不是0才相加。是0无论
matrix[i][j] = (char) (matrix[i-1][j] + 1);
}
}
}
int maxArea = 0;//最大矩形面积
for(int i= 0; i < matrix.length; i++){
maxArea = max(matrix[i],maxArea);//循环求最大
}
return maxArea;
}
/**
* 依据每行。求最大直方图的面积
* @param height char数组
* @param maxArea 当前最大面积
* @return
*/
private int max(char[] height,int maxArea){
if(height.length == 0){//为空直接返回
return maxArea;
}
/**
* 两个栈，分别存在高度和索引
*/
Stack<Character> stHeight = new Stack<Character>();
Stack<Integer> stIndex = new Stack<Integer>();
/**
* 遍历
*/
for(int i = 0 ; i < height.length; i++){
//栈为空。或者高度比栈顶高度大，入栈
if(stHeight.isEmpty() || height[i] > stHeight.peek()){
stHeight.push(height[i]);
stIndex.push(i);
}else if(height[i] < stHeight.peek()){//高度比栈顶高度小
int lastIndex = 0;//最后的索引值
while(!(stHeight.isEmpty()) && height[i] < stHeight.peek()){
lastIndex = stIndex.pop();
int area = (stHeight.pop() - '0')*(i - lastIndex);//计算面积
maxArea = maxArea < area ? area:maxArea;
}
stHeight.push(height[i]);//当前值入栈
stIndex.push(lastIndex);//最小索引入栈
}
}
//假设栈不为空。继续计算
while(!(stHeight.isEmpty())){
int area = (stHeight.pop() - '0')*(height.length - stIndex.pop());
maxArea = maxArea < area ? area:maxArea;
}
return maxArea;
}
}
详细代码和思路例如以下：