题目：Maximal Rectangle
找到最大的全1矩阵。
1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
思路：
要求上面的解，先看下面的问题：
一个数组A[]={5,6,7,8,3};对应如下的直方图，求他的最大矩形的面积。
普通的思路，就是循环遍历，i=0~a.length-1；
然后里面从j=i~a.length-1,在最里层循环中，找到i到j的最小高度，求出它的矩阵面积，然后和最大值比较。
如此就能找到最大面积。
private int largestRectangleArea(int[] height){ int[] min = new int[height.length];//记录i~j的最小高度 int max = 0; for (int i = 0; i < height.length; i++) { //最好的情况都无法超过最大面积，则跳过 if(height[i] > 0 && max/height[i] >= height.length - i)continue; for(int j = i;j < height.length;j++){ //找到i到j的最小高度 if(i == j)min[j] = height[j]; else if(height[j] < min[j - 1])min[j] = height[j]; else min[j] = min[j - 1]; //i到j的矩阵面积 int curArea = min[j]*(j - i + 1); if(curArea > max) max = curArea; } } return max; }
用栈可以优化它的搜索速度。
1） 遍历高度数组，当数组的值是递增（即当前的高度大于栈顶的元素对应的高度）的状态或栈为空，就将当前高度下标入栈，下标加1。
2） 当数组元素不是递增时，即当前的高度小于栈顶元素对应的高度时，弹出该元素，求当前数组元素的前一个元素与当前栈顶元素的矩形面积Height[stack.peek()]*（i - stack.peek() - 1）。
3） 比较该面积和最大面积。
直到1） 再次满足，则入栈。
private int largestRectangleArea2(int[] height){ Stack<Integer> stack = new Stack<Integer>(); int newHeight[] = new int[height.length + 1]; newHeight = Arrays.copyOf(height, height.length + 1); int i = 0,max = 0,num; while(i < newHeight.length){ if(stack.isEmpty() || newHeight[stack.peek()] <= newHeight[i])//栈空或非递增则入栈 stack.push(i++); else{//出栈 int index = stack.pop(); num = stack.isEmpty() ? i : i - stack.peek() - 1; max = Math.max(max, newHeight[index]*num);//求面积并取最大 } } return max; }
有了上面的算法，就可以了求解Maximal Rectangle的问题了。
每一行遍历二维数组，按照下面的规则刷新数组的值：Arr[i][j]=Arr[i-1][j]+Arr[i][j] (Arr[i][j] > 0);
这样就可以得到每一行的直方图，再调用上面的方法求得最大面积。
package com.example.medium; import java.util.Arrays; import java.util.Stack; /** * 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. * @author FuPing * */ public class MaximalRectangle { private int largestRectangleArea(int[] height){ int[] min = new int[height.length];//记录i~j的最小高度 int max = 0; for (int i = 0; i < height.length; i++) { //最好的情况都无法超过最大面积，则跳过 if(height[i] > 0 && max/height[i] >= height.length - i)continue; for(int j = i;j < height.length;j++){ //找到i到j的最小高度 if(i == j)min[j] = height[j]; else if(height[j] < min[j - 1])min[j] = height[j]; else min[j] = min[j - 1]; //i到j的矩阵面积 int curArea = min[j]*(j - i + 1); if(curArea > max) max = curArea; } } return max; } private int largestRectangleArea2(int[] height){ Stack<Integer> stack = new Stack<Integer>(); int newHeight[] = new int[height.length + 1]; newHeight = Arrays.copyOf(height, height.length + 1); int i = 0,max = 0,num; while(i < newHeight.length){ if(stack.isEmpty() || newHeight[stack.peek()] <= newHeight[i])//栈空或递增则入栈 stack.push(i++); else{//出栈 int index = stack.pop(); num = stack.isEmpty() ? i : i - stack.peek() - 1; max = Math.max(max, newHeight[index]*num);//求面积并取最大 } } return max; } public int maximalRectangle(char[][] matrix) { if(matrix == null || matrix.length == 0)return 0; int[][] intMatrix = new int[matrix.length][matrix[0].length]; for (int i = 0; i < intMatrix.length; i++) {//转换成int的二维数组 for (int j = 0; j < intMatrix[0].length; j++) { intMatrix[i][j] = matrix[i][j] - 48; } } for(int j = 0;j < intMatrix[0].length;j++){//将每行转换成直方图 for (int i = 1; i < intMatrix.length; i++) { if(intMatrix[i][j] != 0)//当前元素非零时，统计当前元素上面不为1的高度 intMatrix[i][j] += intMatrix[i - 1][j]; } } int max = 0,lineMax = 0; for (int i = 0; i < intMatrix.length; i++){ lineMax = largestRectangleArea2(intMatrix[i]);//求每一行的最大面积 if(lineMax > max)max = lineMax; } return max; } public static void main(String[] args) { // TODO Auto-generated method stub /*char[][] matrix = new char[][]{{'1','1','1','1','1','1','1','0'}, {'1','1','1','1','1','1','1','0'}, {'1','1','1','1','1','1','1','0'}, {'1','1','1','1','1','0','0','0'}, {'0','1','1','1','1','0','0','0'}};*/ char[][] matrix = new char[][]{{'1','0','1','0','0'}, {'1','0','1','1','1'}, {'1','1','1','1','1'}, {'1','0','0','1','0'}}; for(char[] a : matrix){ for(char ch :a) System.out.print(ch); System.out.println(); } MaximalRectangle rectangle = new MaximalRectangle(); int area = rectangle.maximalRectangle(matrix); System.out.println(area); } }
题目：Maximal Square
找到最大的全1方阵。
思路：
首先按照上面的方法的到每一行的高度直方图，然后求行最大方阵，最后比较每个行最大方阵，得到最大的方阵。
int LeetCode::maximalSquare(vector<vector<char>>& matrix){ if(!matrix.size() || !matrix.at(0).size())return 0;//边为0 vector<int>height(matrix.at(0).size() + 1, 0);//比matrix宽1，这样可以保证最后的一个数为0使得栈最后一定能清空 int maxArea = 0; for (size_t i = 0; i < matrix.size(); i++){ for (size_t j = 0; j < matrix.at(i).size(); j++){ if (matrix.at(i).at(j) == '1'){//在上一行的height基础上加一 height.at(j) += 1; } else{//从零开始 height.at(j) = 0; } } //一行的高度计算完,下面求一行的最大面积 int j = 0, width = 0; stack<int>s; while (j < height.size()){ if (s.empty() || height.at(s.top()) <= height.at(j)){//栈空或递增时入栈 s.push(j); ++j; } else{ int pos = s.top(); s.pop(); width = s.empty() ? j : j - s.top() - 1;//用当前坐标j去减，数组下标从零开始，所以要再加一 width = min(width, height.at(pos));//宽高中选择较小的作为正方形的边 maxArea = max(width*width, maxArea);//求正方形的面积 } } } return maxArea; }