Related: LeetCode 221 - Max Square: Maximum size square sub-matrix with all 1s
Related: LeetCode 84 - Largest Rectangle in Histogram
My Leetcode: Maximal Rectangle (Java)
https://leetcode.com/problems/maximal-rectangle/
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
we can apply a helper table to convert matrix to another int[][] helper with calculate the current height for 1 at each column until current row.
Such as
char[][] matrix -> int[][] helper
X. DP
https://leetcode.com/problems/maximal-rectangle/discuss/29054/Share-my-DP-solution
http://leetcode.tanglei.name/content/matrix/Maximal-Rectangle.html
X. O(n^3) 算法
https://discuss.leetcode.com/topic/1122/my-o-n-3-solution-for-your-reference
https://discuss.leetcode.com/topic/21308/my-java-o-n-3-solution-that-passes-online-judge
一种直接的方法是: 横向记录从左到i, 包括i为1的连续1的长度，然后再纵向去查找以这个连续1长度作为min宽的最大的高度,得到面积。O(n^3)
For every node in the 2-D array, checks all possible rectangles ending at this node (which mean check all the way up/left).
Start with a corner point [i][j], since it is the bottom right corner, the rectangle search direction is left and up.
For the left we already have the number of contiguous 1s ones[i][j]. How to get the height? We need to scan all the values above ones[i][j], it is from i-1 to 0. If meets 0, then stop, else compute the possible rectangle area, and store the max. To compute the area, the minimum length of rectangle should be compared and stores every time.
http://codeluli.blogspot.com/2013/02/maximal-rectangle.html
Brute force: https://github.com/wzhishen/cracking-the-coding-interview/blob/master/src/chap18/Q12.java
http://www.hawstein.com/posts/20.12.html
Related: LeetCode 84 - Largest Rectangle in Histogram
My Leetcode: Maximal Rectangle (Java)
https://leetcode.com/problems/maximal-rectangle/
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
Example:
Input: [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] Output: 6Similar question with largest rectangle in histogram but more tough.
we can apply a helper table to convert matrix to another int[][] helper with calculate the current height for 1 at each column until current row.
Such as
char[][] matrix -> int[][] helper
0,0,0,1,0 0,0,0,1,0
0,1,1,0,1 0,1,1,0,1
0,1,1,1,0 0,2,2,1,0
0,0,1,0,1 0,0,3, 0,1
then we can apply the method used in largest rectangle in histogram to get max area which used current row as bottom then keep updating max area.
https://leetcode.com/discuss/52670/solution-based-maximum-rectangle-histogram-with-explanation
https://discuss.leetcode.com/topic/1634/a-o-n-2-solution-based-on-largest-rectangle-in-histogram/2
https://leetcode.com/discuss/5198/a-o-n-2-solution-based-on-largest-rectangle-in-histogram
public int maximalRectangle(char[][] matrix) { if (matrix==null||matrix.length==0||matrix[0].length==0) return 0; int cLen = matrix[0].length; // column length int rLen = matrix.length; // row length // height array int[] h = new int[cLen+1]; h[cLen]=0; int max = 0; for (int row=0;row<rLen;row++) { Stack<Integer> s = new Stack<Integer>(); for (int i=0;i<cLen+1;i++) { if (i<cLen) if(matrix[row][i]=='1') h[i]+=1; else h[i]=0; if (s.isEmpty()||h[s.peek()]<=h[i]) s.push(i); else { while(!s.isEmpty()&&h[i]<h[s.peek()]){ int top = s.pop(); int area = h[top]*(s.isEmpty()?i:(i-s.peek()-1)); if (area>max) max = area; } s.push(i); } } } return max; }
http://algobox.org/maximal-rectangle/
int area = 0; int numRows = matrix.length; if (numRows == 0) return 0; int numCols = matrix[0].length; if (numCols == 0) return 0; int [][] rowArea = new int[numRows][numCols]; for (int i = 0; i < numRows; i++) { // y for (int j = 0; j < numCols; j++) { if (matrix[i][j] == '0') continue; else { if (j == 0) rowArea[i][j] = 1; else { rowArea[i][j] = rowArea[i][j-1] + 1; } int y = 1; int x = numCols; while(i-y+1 >= 0 && rowArea[i-y+1][j] > 0) { x = Math.min(x, rowArea[i-y+1][j]); area = Math.max(area, x*y); y++; } } } } return area; }
http://www.cnblogs.com/lichen782/p/leetcode_maximal_rectangle.html
https://discuss.leetcode.com/topic/1634/a-o-n-2-solution-based-on-largest-rectangle-in-histogram/2
We can apply the maximum in histogram in each row of the 2D matrix. What we need is to maintain an int array for each row, which represent for the height of the histogram.
Please refer to https://leetcode.com/problems/largest-rectangle-in-histogram/ first.
Suppose there is a 2D matrix like
1 1 0 1 0 1
0 1 0 0 1 1
1 1 1 1 0 1
1 1 1 1 0 1
First initiate the height array as 1 1 0 1 0 1, which is just a copy of the first row. Then we can easily calculate the max area is 2.
Then update the array. We scan the second row, when the matrix[1][i] is 0, set the height[i] to 0; else height[i] += 1, which means the height has increased by 1. So the height array again becomes 0 2 0 0 1 2. The max area now is also 2.
Apply the same method until we scan the whole matrix. the last height arrays is 2 4 2 2 0 2, so the max area has been found as 2 * 4 = 8.
Then reason we scan the whole matrix is that the maximum value may appear in any row of the height.
public int maximalRectangle(char[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
int[] height = new int[matrix[0].length];
for(int i = 0; i < matrix[0].length; i ++){
if(matrix[0][i] == '1') height[i] = 1;
}
int result = largestInLine(height);
for(int i = 1; i < matrix.length; i ++){
resetHeight(matrix, height, i);
result = Math.max(result, largestInLine(height));
}
return result;
}
private void resetHeight(char[][] matrix, int[] height, int idx){
for(int i = 0; i < matrix[0].length; i ++){
if(matrix[idx][i] == '1') height[i] += 1;
else height[i] = 0;
}
}
public int largestInLine(int[] height) {
if(height == null || height.length == 0) return 0;
int len = height.length;
Stack<Integer> s = new Stack<Integer>();
int maxArea = 0;
for(int i = 0; i <= len; i++){
int h = (i == len ? 0 : height[i]);
if(s.isEmpty() || h >= height[s.peek()]){
s.push(i);
}else{
int tp = s.pop();
maxArea = Math.max(maxArea, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));
i--;
}
}
return maxArea;
}https://leetcode.com/discuss/5198/a-o-n-2-solution-based-on-largest-rectangle-in-histogram
public int maximalRectangle(char[][] matrix) { if (matrix==null||matrix.length==0||matrix[0].length==0) return 0; int cLen = matrix[0].length; // column length int rLen = matrix.length; // row length // height array int[] h = new int[cLen+1]; h[cLen]=0; int max = 0; for (int row=0;row<rLen;row++) { Stack<Integer> s = new Stack<Integer>(); for (int i=0;i<cLen+1;i++) { if (i<cLen) if(matrix[row][i]=='1') h[i]+=1; else h[i]=0; if (s.isEmpty()||h[s.peek()]<=h[i]) s.push(i); else { while(!s.isEmpty()&&h[i]<h[s.peek()]){ int top = s.pop(); int area = h[top]*(s.isEmpty()?i:(i-s.peek()-1)); if (area>max) max = area; } s.push(i); } } } return max; }
http://algobox.org/maximal-rectangle/
The solution is based on “Largest Rectangle in Histogram” solution. Every row in the matrix is viewed as the ground with some buildings on it. The building height is the count of consecutive 1s from that row to above rows. The rest is then the same as this.
def maximalRectangle(self, matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
height = [0] * (n + 1)
ans = 0
for row in matrix:
for i in xrange(n):
height[i] = height[i] + 1 if row[i] == '1' else 0
stack = [-1]
for i in xrange(n + 1):
while height[i] < height[stack[-1]]:
h = height[stack.pop()]
w = i - 1 - stack[-1]
ans = max(ans, h * w)
stack.append(i)
return ans
TODO:https://leetcode.com/discuss/3395/my-o-n-3-solution-for-your-referenceint area = 0; int numRows = matrix.length; if (numRows == 0) return 0; int numCols = matrix[0].length; if (numCols == 0) return 0; int [][] rowArea = new int[numRows][numCols]; for (int i = 0; i < numRows; i++) { // y for (int j = 0; j < numCols; j++) { if (matrix[i][j] == '0') continue; else { if (j == 0) rowArea[i][j] = 1; else { rowArea[i][j] = rowArea[i][j-1] + 1; } int y = 1; int x = numCols; while(i-y+1 >= 0 && rowArea[i-y+1][j] > 0) { x = Math.min(x, rowArea[i-y+1][j]); area = Math.max(area, x*y); y++; } } } } return area; }
http://www.cnblogs.com/lichen782/p/leetcode_maximal_rectangle.html
public int maximalRectangle2(char[][] matrix) { 2 int m = matrix.length; 3 int n = m == 0 ? 0 : matrix[0].length; 4 int[][] height = new int[m][n + 1]; 5 //actually we know that height can just be a int[n+1], 6 //however, in that case, we have to write the 2 parts together in row traverse, 7 //which, leetcode just doesn't make you pass big set 8 //所以啊，leetcode是喜欢分开写循环的，即使时间复杂度一样，即使可以节约空间 9 int maxArea = 0; 10 for(int i = 0; i < m; i++){ 11 for(int j = 0; j < n; j++) { 12 if(matrix[i][j] == '0'){ 13 height[i][j] = 0; 14 }else { 15 height[i][j] = i == 0 ? 1 : height[i - 1][j] + 1; 16 } 17 } 18 } 19 for(int i = 0; i < m; i++){ 20 int area = maxAreaInHist(height[i]); 21 if(area > maxArea){ 22 maxArea = area; 23 } 24 } 25 return maxArea; 26 } 28 private int maxAreaInHist(int[] height){ 29 Stack<Integer> stack = new Stack<Integer>(); 30 int i = 0; 31 int maxArea = 0; 32 while(i < height.length){ 33 if(stack.isEmpty() || height[stack.peek()] <= height[i]){ 34 stack.push(i++); 35 }else { 36 int t = stack.pop(); 37 maxArea = Math.max(maxArea, height[t] * (stack.isEmpty() ? i : i - stack.peek() - 1)); 38 } 39 } 40 return maxArea; 41 }
int largestRectangleArea(const vector<int> &height)
{
int result = 0;
stack<int> index;
for(int i = 0; i < height.size(); i++)
{
if(index.empty() || height[index.top()] <= height[i] )
index.push(i);
else
{
while(!index.empty() && height[index.top()] >= height[i])
{
auto t = index.top();
index.pop();
result = std::max(result, height[t] * (index.empty() ? i : (i-1)-index.top()));
}
index.push(i);//Do not forget.
}
}
return result;
}
int maximalRectangle(vector<vector<char> > &matrix)
{
int m = matrix.size(); if(m == 0) return 0;
int n = matrix[0].size();
vector<vector<int> > ones(m, vector<int>(n, 0));
int result = 0;
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
if(i == 0) ones[0][j] = matrix[i][j] == '1' ? 1 : 0;
else ones[i][j] = matrix[i][j] == '1' ? ones[i-1][j]+1 : 0;
}
ones[i].push_back(-1);
result = std::max(result, largestRectangleArea(ones[i]));
}
return result;
} int maximalRectangle(vector<vector<char> > &matrix)
{
int m = matrix.size(); if(m == 0) return 0;
int n = matrix[0].size();
int result = 0;
vector<int> leftMax(n, -1);
vector<int> rightMin(n, n);
vector<int> height(n, 0);
for(int i = 0; i < m; i++)
{
int left = -1, right = n;
for(int j = 0; j < n; j++)
{
if(matrix[i][j] == '1'){
++height[j];
leftMax[j] = std::max(leftMax[j], left);
}else{
left = j;
height[j]=0; leftMax[j]=-1; rightMin[j]=n;
}
}
for(int j = n-1; j >= 0; j--)
{
if(matrix[i][j] == '1'){
rightMin[j] = std::min(rightMin[j], right);
result = std::max(result, height[j]*(rightMin[j]-leftMax[j]-1));
}else{
right = j;
}
}
}
return result;
}X. DP
https://leetcode.com/problems/maximal-rectangle/discuss/29054/Share-my-DP-solution
The DP solution proceeds row by row, starting from the first row. Let the maximal rectangle area at row i and column j be computed by [right(i,j) - left(i,j)]*height(i,j).
All the 3 variables left, right, and height can be determined by the information from previous row, and also information from the current row. So it can be regarded as a DP solution. The transition equations are:
left(i,j) = max(left(i-1,j), cur_left), cur_left can be determined from the current row
right(i,j) = min(right(i-1,j), cur_right), cur_right can be determined from the current row
height(i,j) = height(i-1,j) + 1, if matrix[i][j]=='1';
height(i,j) = 0, if matrix[i][j]=='0'
The code is as below. The loops can be combined for speed but I separate them for more clarity of the algorithm
If you think this algorithm is not easy to understand, you can try this example:
0 0 0 1 0 0 0
0 0 1 1 1 0 0
0 1 1 1 1 1 0
The vector "left" and "right" from row 0 to row 2 are as follows
row 0:
l: 0 0 0 3 0 0 0
r: 7 7 7 4 7 7 7
row 1:
l: 0 0 2 3 2 0 0
r: 7 7 5 4 5 7 7
row 2:
l: 0 1 2 3 2 1 0
r: 7 6 5 4 5 6 7
The vector "left" is computing the left boundary. Take (i,j)=(1,3) for example. On current row 1, the left boundary is at j=2. However, because matrix[1][3] is 1, you need to consider the left boundary on previous row as well, which is 3. So the real left boundary at (1,3) is 3.
int maximalRectangle(vector<vector<char> > &matrix) {
if(matrix.empty()) return 0;
const int m = matrix.size();
const int n = matrix[0].size();
int left[n], right[n], height[n];
fill_n(left,n,0); fill_n(right,n,n); fill_n(height,n,0);
int maxA = 0;
for(int i=0; i<m; i++) {
int cur_left=0, cur_right=n;
for(int j=0; j<n; j++) { // compute height (can do this from either side)
if(matrix[i][j]=='1') height[j]++;
else height[j]=0;
}
for(int j=0; j<n; j++) { // compute left (from left to right)
if(matrix[i][j]=='1') left[j]=max(left[j],cur_left);
else {left[j]=0; cur_left=j+1;}
}
// compute right (from right to left)
for(int j=n-1; j>=0; j--) {
if(matrix[i][j]=='1') right[j]=min(right[j],cur_right);
else {right[j]=n; cur_right=j;}
}
// compute the area of rectangle (can do this from either side)
for(int j=0; j<n; j++)
maxA = max(maxA,(right[j]-left[j])*height[j]);
}
return maxA;
}
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) return 0;
int m = matrix.length;
int n = matrix[0].length;
int[] left = new int[n]; // left boundary of histogram columns.
int[] right = new int[n]; // right boundary of histogram columns.
int[] height = new int[n]; // height of histogram columns.
Arrays.fill(right, n);
int area = 0;
for (int i = 0; i < m; i++) {
int l = 0, r = n;
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
height[j]++;
left[j] = Math.max(l, left[j]);
}
else {
l = j + 1;
height[j] = 0;
left[j] = 0;
right[j] = n;
}
}
for (int j = n - 1; j >= 0; j--) {
if (matrix[i][j] == '1') {
right[j] = Math.min(r, right[j]);
area = Math.max(area, height[j] * (right[j] - left[j]));
}
else {
r = j;
}
}
}
return area;
}
1、求高：用height(i,j)表示点(i,j)的高度：
height(i,j) = height(i-1,j) + 1, if matrix[i][j]=='1';
height(i,j) = 0, if matrix[i][j]=='0'
如对于：
得到：
2、求最左边界和最右边界：求出每一个点的高后，对于点(i,j)首先考虑以height(i,j)为高的矩形的最左边界left(i,j)，这个最左边界由两个东西决定，上一个点的最左边界和(i,j)点所在行中改能够到达的最左边界(currLeft)。
最左边界不能超过上一点的最左边界和本行的最左边界；
for(int j=0;j<n;j++){
if(matrix[i][j] == '1'){
left[j] = max(left[j],currLeft);
}else{
left[j]=0;
currLeft = j+1;
} }
相同的原理，最右边界为：
for(int j=n-1;j>=0;j--){
if(matrix[i][j] == '1'){
right[j] = min(right[j],currRight);
}else{
right[j]=n;
currRight = j;
}
}
3、求最大面积：最后根据最右边界和最左边界求出宽，再根据已求得的高得出面积。遍历，求出最大面积。
注意：对于(i,j)点，Area(i,j)并不是以(i,j)为右下角的最大矩形，如左边一个红色的点，显然以其为右下角的最大矩形面积是3而不是6。Area(i,j)表示的是以height(i,j)为高，向(i,j)左右延伸的最大矩形面积。图中彩色框对于的就是相应颜色点的最大矩形。
int maximalRectangle(vector<vector<char> > &matrix) {
if(matrix.empty()) return 0;
const int m = matrix.size();
const int n = matrix[0].size();
int left[n], right[n], height[n];
fill_n(left,n,0); fill_n(right,n,n); fill_n(height,n,0);
int maxA = 0;
for(int i=0; i<m; i++) {
int currLeft=0;
int currRight = n;
for(int j=0; j<n;j++){
if(matrix[i][j] == '1'){
height[j] += 1;
}else{
height[j] = 0;
}
}
for(int j=0;j<n;j++){
if(matrix[i][j] == '1'){
left[j] = max(left[j],currLeft);
}else{
left[j]=0;
currLeft = j+1;
}
}
for(int j=n-1;j>=0;j--){
if(matrix[i][j] == '1'){
right[j] = min(right[j],currRight);
}else{
right[j]=n;
currRight = j;
}
}
for(int j=0;j<n;j++){
maxA = max(maxA,height[j]*(right[j]-left[j]));
}
}
return maxA;
}
}
思路同样是从第一行开始一行一行地处理，使[i, j]处最大子矩阵的面积是(right(i, j)-left(i, j))*height(i, j)。其中height统计当前位置及往上'1'的数量；left和right是高度是当前点的height值得左右边界，即是以当前点为中心，以height为高度向两边扩散的左右边界。
递推公式如下：
left(i, j) = max(left(i-1, j), cur_left);
right(i, j) = min(right(i-1, j), cur_right);
height(i, j) = height(i-1, j) + 1, if matrix[i][j]=='1';
height(i, j) = 0, if matrix[i][j]=='0'.
其中cur_left和cur_right的值由当前行决定，如果当前位置是'1'，则cur_left和cur_right都不变；如果当前位置是'0'，则cur_left就为当前位置的右侧，cur_right就为当前位置（因为左闭右开）。
4 int maximalRectangle(vector<vector<char> > &matrix)
5 {
6 if(matrix.size() == 0 || matrix[0].size() == 0)
7 return 0;
8
9 int m = matrix.size(), n = matrix[0].size(), res = 0;
10 vector<int> left(n, 0), right(n, n), height(n, 0);
11
12 for(int i = 0; i < m; ++ i)
13 {
14 int cur_left = 0, cur_right = n;
15
16 for(int j = 0; j < n; ++ j)
17 height[j] = matrix[i][j] == '1' ? height[j] + 1 : 0;
18
19 for(int j = 0; j < n; ++ j)
20 {
21 left[j] = matrix[i][j] == '1' ? max(left[j], cur_left) : 0;
22 cur_left = matrix[i][j] == '1' ? cur_left : j + 1;
23 }
24
25 for(int j = n - 1; j >= 0; -- j)
26 {
27 right[j] = matrix[i][j] == '1' ? min(right[j], cur_right) : n;
28 cur_right = matrix[i][j] == '1' ? cur_right : j;
29 }
30
31 for(int j = 0; j < n; ++ j)
32 res = max(res, (right[j] - left[j]) * height[j]);
33 }
34
35 return res;
36 }
The DP solution proceeds row by row, starting from the first row. Let the maximal rectangle area at row i and column j be computed by [right(i,j) - left(i,j)]*height(i,j).
All the 3 variables left, right, and height can be determined by the information from previous row, and also information from the current row. So it can be regarded as a DP solution. The transition equations are:
left(i,j) = max(left(i-1,j), cur_left), cur_left can be determined from the current row
right(i,j) = min(right(i-1,j), cur_right), cur_right can be determined from the current row
height(i,j) = height(i-1,j) + 1, if matrix[i][j]=='1';
height(i,j) = 0, if matrix[i][j]=='0'
The code is as below. The loops can be combined for speed but I separate them for more clarity of the algorithm.
int maximalRectangle(vector<vector<char> > &matrix) {
if(matrix.empty()) return 0;
const int m = matrix.size();
const int n = matrix[0].size();
int left[n], right[n], height[n];
fill_n(left,n,0); fill_n(right,n,n); fill_n(height,n,0);
int maxA = 0;
for(int i=0; i<m; i++) {
int cur_left=0, cur_right=n;
for(int j=0; j<n; j++) { // compute height (can do this from either side)
if(matrix[i][j]=='1') height[j]++;
else height[j]=0;
}
for(int j=0; j<n; j++) { // compute left (from left to right)
if(matrix[i][j]=='1') left[j]=max(left[j],cur_left);
else {left[j]=0; cur_left=j+1;}
}
// compute right (from right to left)
for(int j=n-1; j>=0; j--) {
if(matrix[i][j]=='1') right[j]=min(right[j],cur_right);
else {right[j]=n; cur_right=j;}
}
// compute the area of rectangle (can do this from either side)
for(int j=0; j<n; j++)
maxA = max(maxA,(right[j]-left[j])*height[j]);
}
return maxA;
}
I read your solution and come up with a similar DP solution, with slightly different explanation:
Scan elements by row, calculate max distance from current element(inclusive of itself) to a top, left, right non-0 elements. Calculations from prev row can be used to calculate current row.
top(y,x) = top(y-1,x)+1 if matrix(y,x) == 1; else reset to default (0)
left(y,x) = min(left(y-1,x), max_left_distance_so_far) if matrix(y,x) == 1; else reset to default
right(y,x) = min(right(y+1,x), max_right_distance_so_far) if matrix(y,x) == 1; else reset to default
area(y,x) = (left(y,x)+right(y,x)-1)*top(y,x) if matrix(y,x) == 1
- left distance should be calculated from left to right, and right distance from right to left
- as we use
minto calculate left & right distances, their default values should be some big enough number - since left & right distances are inclusive of current element, we should -1 when calculating width to avoid double counting
public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) { return 0; }
int rows = matrix.length, cols = matrix[0].length;
int[] left = new int[cols], right = new int[cols], top = new int[cols];
Arrays.fill(left, cols); // max distance (inclusive) to left-most 1 at (y,x)
Arrays.fill(right, cols); // max distance (inclusive) to right-most 1 at (y,x)
Arrays.fill(top, 0); // max distance (inclusive) to top-most 1 at (y,x)
int max = 0;
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
if (matrix[y][x] == '1') { top[x] += 1; }
else { top[x] = 0; }
}
int l = 0; // max left distance so far
for (int x = 0; x < cols; x++) {
if (matrix[y][x] == '1') { left[x] = Math.min(left[x], ++l); }
else { left[x] = cols; l = 0; }
}
int r = 0; // max right distance so far
for (int x = cols-1; x >= 0; x--) {
if (matrix[y][x] == '1') { right[x] = Math.min(right[x], ++r); }
else { right[x] = cols; r = 0; }
}
for (int x = 0; x < cols; x++) {
if (matrix[y][x] == '1') {
// width should exclude double count of current element
max = Math.max(max, (left[x]+right[x]-1)*top[x]);
}
}
}
return max;
} int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size();
if(m==0) return 0;
int n = matrix[0].size();
//bool dp[m][n][m+1][n+1];
bool dp[2][n+1];
int maxRectangle = 0;
for(int i = 0;i<m;i++){
for(int j = 0;j<n;j++){
if(matrix[i][j] == '0') continue;
for(int xLen = 1;i+xLen-1 < m;xLen++){
for(int yLen = 1;j+yLen-1 < n;yLen++){
if(matrix[i+xLen-1][j+yLen-1] == '0') {
dp[0][yLen] = false;
break;
}
if(xLen == 1 && yLen == 1)
//dp[i][j][xLen][yLen] = true;
dp[1][yLen] = true;
else if(xLen == 1 && yLen != 1){
//dp[i][j][xLen][yLen] = dp[i][j][xLen][yLen-1];
dp[1][yLen] = dp[1][yLen-1];
}else if(xLen != 1 && yLen == 1){
dp[1][yLen] = dp[0][yLen];
}else{
dp[1][yLen] = dp[1][yLen-1] && dp[0][yLen];
}
if(dp[1][yLen]) {maxRectangle = max(xLen * yLen,maxRectangle);
dp[0][yLen] = dp[1][yLen];}
else break;
}
}
}
}
return maxRectangle;
}http://leetcode.tanglei.name/content/matrix/Maximal-Rectangle.html
X. O(n^3) 算法
https://discuss.leetcode.com/topic/1122/my-o-n-3-solution-for-your-reference
https://discuss.leetcode.com/topic/21308/my-java-o-n-3-solution-that-passes-online-judge
int maximalRectangle(vector<vector<char> > &matrix) {
int num_i=matrix.size();
if (num_i==0) return 0;
int num_j=matrix[0].size();
if (num_j==0) return 0;
vector<vector<int>> max_x(num_i,vector<int>(num_j,0)); //number of consecutive 1s to the left of matrix[i][j], including itself
int area=0;
for (int i=0;i<num_i;i++){
for (int j=0;j<num_j;j++){
if (matrix[i][j]=='1'){
if (j==0) max_x[i][j]=1;
else max_x[i][j]=max_x[i][j-1]+1;
int y=1;
int x=num_j;
while((i-y+1>=0)&&(matrix[i-y+1][j]=='1')){
x=min(x, max_x[i-y+1][j]);
area=max(area,x*y);
y++;
}
}
}
}
return area;
}一种直接的方法是: 横向记录从左到i, 包括i为1的连续1的长度，然后再纵向去查找以这个连续1长度作为min宽的最大的高度,得到面积。O(n^3)
- 先用dp求一个新矩阵，d[i][j]表示以(i, j)结尾有几个连续1（在当前row)。
- 然后遍历这个新矩阵，在每个cell，都看看“宽度是d[i][j]的矩阵最多能有多高？“，也就是往上expand到宽度变窄为止，往下expand到宽度变窄为止，然后总高度×当前宽度就是d[i][j]所属于的矩阵的最大面积。这就是个O(M * N) * O(M)。
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0)
return 0;
int res = 0;
int m = matrix.length, n = matrix[0].length;
int[][] d = new int[m][n];
for (int i = 0; i < m; i++) {
d[i][0] = matrix[i][0] - '0';
for (int j = 1; j < n; j++) {
d[i][j] = matrix[i][j] == '1' ? d[i][j - 1] + 1 : 0;
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
res = Math.max(res, expand(d, i, j));
}
}
return res;
}
private int expand(int[][] d, int I, int J) {
int height = 0;
int width = d[I][J];
//go up
for (int i = I - 1; i >= 0; i--) {
if (d[i][J] >= width) {
height++;
} else {
break;
}
}
//go down
for (int i = I; i < d.length; i++) {
if (d[i][J] >= width) {
height++;
} else {
break;
}
}
return width * height;
}
http://blog.csdn.net/fightforyourdream/article/details/17711893For every node in the 2-D array, checks all possible rectangles ending at this node (which mean check all the way up/left).
Start with a corner point [i][j], since it is the bottom right corner, the rectangle search direction is left and up.
For the left we already have the number of contiguous 1s ones[i][j]. How to get the height? We need to scan all the values above ones[i][j], it is from i-1 to 0. If meets 0, then stop, else compute the possible rectangle area, and store the max. To compute the area, the minimum length of rectangle should be compared and stores every time.
public static int maximalRectangle(char[][] matrix) {
int rows = matrix.length;
if(rows == 0){
return 0;
}
int cols = matrix[0].length;
// 先计算全1矩阵的宽度
int[][] hOnes = new int[rows][cols]; // horizontal ones
int max = 0; // 最大面积
for(int i=0; i<rows; i++){
for(int j=0; j<cols; j++){
if(matrix[i][j] == '1'){
if(j == 0){ // 特殊处理左起第一个
hOnes[i][j] = 1;
}else{
hOnes[i][j] = hOnes[i][j-1] + 1;
}
}
}
}
for(int i=0; i<rows; i++){
for(int j=0; j<cols; j++){
if(hOnes[i][j] != 0){
int minI = i; // 计算高度，minI不断向上走
int minRowWidth = hOnes[i][j]; // 随着向上走，宽度也要随之调整
while(minI >= 0){
minRowWidth = Math.min(minRowWidth, hOnes[minI][j]);
int area = minRowWidth * (i-minI+1);
max = Math.max(max, area);
minI--;
}
}
}
}
return max;
}
http://codeluli.blogspot.com/2013/02/maximal-rectangle.html
//Solution 3: build a cache to make this problem to a list of "Largest Rectangle in Histogram" in M layers //will take O(M*N^2) time and O(M) space public class Solution { public int maximalRectangle(char[][] matrix) { // Start typing your Java solution below // DO NOT write main() function int y = matrix.length; if(y == 0) return 0; int max = 0; int x = matrix[0].length; int[] cache = new int[x]; for(int i = y-1; i >= 0; i--){ updateCache(matrix, i, cache); max = Math.max(max, getArea(i, cache)); } return max; } public void updateCache(char[][] matrix, int layer, int[] cache){ for(int i = 0; i < matrix[0].length; i++){ if(matrix[layer][i] == '1') cache[i] += 1; else cache[i] = 0; } } public int getArea(int layer, int[] cache){ int max = 0; Stack<Integer> stack = new Stack<Integer>(); for(int i = 0; i < cache.length; i++){ int h = cache[i]; if(stack.isEmpty() || stack.peek() <= h) stack.push(h); else{ int count = 0; while(!stack.isEmpty() && stack.peek() > h){ count ++; max = Math.max(max, stack.pop()*count); } while(count >= 0){ stack.push(h); count --; } } } int count = 0; while(!stack.isEmpty()){ count ++; max = Math.max(max, stack.pop()*count); } return max; } } //Solution 4: I saw an optimal solution using O(M) space takes O(M^N) time. //But the method used there is sort of unique so not quite helpful to solving other problems. Or maybe I`m just not strong enough to obsorb it :( //If you are interested refer to : //http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529 //After all, solution 3 will be at least not bad for a tough interview. //And the ability of breaking down a big and new problem to one or more familiar problems is a must-have for a good engineer.
//Solution2: consideration: if an element is '0', all areas containing it will not be valid //start from each valid element and use it as a base to expand to its possible largest area //O(M^2 * N^2) public class Solution { public int maximalRectangle(char[][] matrix) { // Start typing your Java solution below // DO NOT write main() function int y = matrix.length; if(y == 0) return 0; int max = 0; int x = matrix[0].length; for(int i = y-1; i >= 0; i--){ for(int j = 0; j < x; j++){ if(matrix[i][j] == '1'){ max = Math.max(max, getArea(matrix, i, j)); } } } return max; } public int getArea(char[][] matrix, int i, int j){ int max = 0; int base = Integer.MAX_VALUE; int y = i; while(y >= 0){ int width = 0; int x = j; while(x < matrix[0].length && matrix[y][x] == '1'){ width ++; x ++; } base = Math.min(width, base); if(base == 0) break; max = Math.max(max, (i-y+1)*base); y--; } return max; } }
//Solution1: brute force, O(M^3 * N^3) public class Solution { public int maximalRectangle(char[][] matrix) { // Start typing your Java solution below // DO NOT write main() function int y = matrix.length; if(y == 0) return 0; int max = 0; int x = matrix[0].length; for(int yFrom = 0; yFrom < y; yFrom++){ for(int yTo = yFrom; yTo < y; yTo++){ for(int xFrom = 0; xFrom < x; xFrom++){ for(int xTo = xFrom; xTo < x; xTo++){ if(isValid(matrix, xFrom, xTo, yFrom, yTo)){ max = Math.max(max, getArea(xFrom, xTo, yFrom, yTo)); } } } } } return max; } public int getArea(int xFrom, int xTo, int yFrom, int yTo){ return (xTo - xFrom + 1) * (yTo - yFrom + 1); } public boolean isValid(char[][] matrix, int xFrom, int xTo, int yFrom, int yTo){ for(int i = yFrom; i <= yTo; i++){ for(int j = xFrom; j <= xTo; j++){ if(matrix[i][j] != '1') return false; } } return true; } }http://blog.csdn.net/u014688145/article/details/70820874
如果有了前面那道题的铺垫，这道题就不难了。但怪就怪在，如果没有前面那道题，你就很难想到！就因为被它的矩阵吓到了？这些认知障碍得破除啊。
它是一个平面，让你求最大长方形面积，所以呢，想法就是把矩阵一层一层往下切。先切出第一层，我们能计算每个位置的高度，为
1 0 1 0 0，然后切第二层2 0 2 1 1，第三层3 1 3 2 2，第四层4 0 0 3 0，这不就是分别求每一层的面积么，数值就是它们的高度，不用解释。
接下来的问题，就是生成这样的矩阵就好了，很简单，一个dp就能搞定
public int maximalRectangle(char[][] matrix) {
int row = matrix.length;
if (row == 0)
return 0;
int col = matrix[0].length;
if (col == 0)
return 0;
int[][] w = new int[row + 1][col + 1];
for (int j = 1; j < col + 1; j++) {
if (matrix[0][j - 1] == '1') {
w[1][j] = 1; // 宽
}
}
for (int i = 2; i < row + 1; i++) {
for (int j = 1; j < col + 1; j++) {
if (matrix[i - 1][j - 1] == '1') {
w[i][j] = w[i-1][j] + 1;
}
}
}
int max = 0;
for (int i = 1; i < row+1; i++){
max = Math.max(max,largestRectangleArea(w[i]));
}
return max;
}
public int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<>();
int max = 0;
for (int i = 0; i <= heights.length; i++) {
int curr = (i == heights.length) ? 0 : heights[i];
int count = 0;
while (!stack.isEmpty() && heights[stack.peek()] > curr) {
int pos = stack.pop();
max = Math.max(max, heights[pos] * (i - pos));
heights[pos] = curr;
count++;
}
i -= count;
stack.push(i);
}
return max;
}Brute force: https://github.com/wzhishen/cracking-the-coding-interview/blob/master/src/chap18/Q12.java
http://www.hawstein.com/posts/20.12.html
Given an NxN matrix of positive and negative integers, write code to find the submatrix with the largest possible sum.
给一个NxN的矩阵，矩阵上每个格子中填有一个整数(正，负或0)， 写代码计算子矩阵之和的最大值。
http://blog.csdn.net/kenden23/article/details/17503899
http://siddontang.gitbooks.io/leetcode-solution/content/array/largest_rectangle_in_histogram.html
http://yyeclipse.blogspot.com/2012/11/solving-maximal-rectangle-problem-based.html
http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529?pgno=1
Read full article from My Leetcode: Maximal Rectangle (Java)
给一个NxN的矩阵，矩阵上每个格子中填有一个整数(正，负或0)， 写代码计算子矩阵之和的最大值。
http://blog.csdn.net/kenden23/article/details/17503899
http://siddontang.gitbooks.io/leetcode-solution/content/array/largest_rectangle_in_histogram.html
http://yyeclipse.blogspot.com/2012/11/solving-maximal-rectangle-problem-based.html
http://www.drdobbs.com/database/the-maximal-rectangle-problem/184410529?pgno=1
Read full article from My Leetcode: Maximal Rectangle (Java)
