Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

https://leetcode.com/problems/maximal-rectangle/

Solution I: brute force O(N^3)

取所有前面最小的延伸距离乘以当前离第一行的行数

http://www.cnblogs.com/lichen782/p/leetcode_maximal_rectangle.html

/* 以给出的坐标作为左上角，计算其中的最大矩形面积 @param matrix @param row 给出坐标的行 @param col 给出坐标的列 @return 返回最大矩形的面积 / private int maxRectangle(char[][] matrix, int row, int col) { int minWidth = Integer.MAX_VALUE; int maxArea = 0; for (int i = row; i < matrix.length && matrix[i][col] == '1'; i++) { int width = 0; while (col + width < matrix[row].length && matrix[i][col + width] == '1') { width++; } if (width < minWidth) {// 如果当前宽度小于了以前的最小宽度，更新它，为下面的矩形计算做准备 minWidth = width; } int area = minWidth (i - row + 1); if (area > maxArea) maxArea = area; } return maxArea; }

Solution II: Optimized O(N^2)

find max area in histogram as a routine to calculate each row

why n+1 in height:

height[i][n] == 0, manually push 0 to stack to calculate all the elements in stack

check the code for max rectangle for histogram

public class Solution { public int maximalRectangle(char[][] matrix) { int m = matrix.length; if (m == 0) { return m; } int n = matrix[0].length; int[][] height = new int[m][n+1]; // why n+1 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == '0') { height[i][j] = 0; } else { height[i][j] = i == 0 ? 1 : height[i-1][j] + 1; } } } int max = 0; for (int i = 0; i < m; i++) { int area = maxInLine(height[i]); max = Math.max(area, max); } return max; } public int maxInLine(int[] height) { int max = 0; Stack<Integer> stack = new Stack<>(); int i = 0; while (i < height.length) { if (stack.isEmpty() || height[i] >= height[stack.peek()]) { stack.push(i); i++; } else { int n = stack.pop(); int curr = height[n] * (stack.isEmpty() ? i : i - stack.peek() - 1); max = Math.max(max, curr); } } return max; } }