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;}}具体代码和思路如下：
版权声明：本文为博主原创文章，未经博主允许不得转载。
莫找借口失败，只找理由成功。(不为失败找理由，要为成功找方法
