Comment on page

# 85.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: 6

## 代码

### Approach #1 Brute Force

Trivially we can enumerate every possible rectangle. This is done by iterating over all possible combinations of coordinates `(x1, y1)` and `(x2, y2)` and letting them define a rectangle with the coordinates being opposite corners. This is too slow to pass all test cases.
`Time: O(N^3)` `Space: O(1)`
public class Solution {
public int largestRectangleArea(int[] heights) {
int maxarea = 0;
for (int i = 0; i < heights.length; i++) {
for (int j = i; j < heights.length; j++) {
int minheight = Integer.MAX_VALUE;
for (int k = i; k <= j; k++)
minheight = Math.min(minheight, heights[k]);
maxarea = Math.max(maxarea, minheight * (j - i + 1));
}
}
return maxarea;
}
}
Better Brote force
`Time: O(N^2)` `Space: O(1)`
public class Solution {
public int largestRectangleArea(int[] heights) {
int maxarea = 0;
for (int i = 0; i < heights.length; i++) {
int minheight = Integer.MAX_VALUE;
for (int j = i; j < heights.length; j++) {
minheight = Math.min(minheight, heights[j]);
maxarea = Math.max(maxarea, minheight * (j - i + 1));
}
}
return maxarea;
}
}

### Approach #2 Dynamic Programming

Complexity Analysis
• Time complexity : O(N^2 * M)
• Space complexity : O(NM)
`dp[i][j] 在第i行中，0 - j 列的最大宽度`
class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) return 0;
int R = matrix.length;
int C = matrix[0].length;
int maxarea = 0;
int[][] dp = new int[R][C];
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (matrix[i][j] == '1') {
if (j == 0) {
dp[i][j] = 1;
} else {
dp[i][j] = dp[i][j - 1] + 1;
}
int width = dp[i][j];
for (int k = i; k >= 0; k--) {
width = Math.min(width, dp[k][j]);
maxarea = Math.max(maxarea, width * (i - k + 1));
}
}
}
}
return maxarea;
}
}

### Approach #3 Using Histograms - Stack

• Time complexity: `O(n)`
• Space complexity: `O(n)`

class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) return 0;
int maxarea = 0;
int[] dp = new int[matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
// update the state of this row's histogram using the last row's histogram
// by keeping track of the number of consecutive ones
dp[j] = matrix[i][j] == '1' ? dp[j] + 1 : 0;
}
// update maxarea with the maximum area from this row's histogram
maxarea = Math.max(maxarea, leetcode84(dp));
}
return maxarea;
}
// Get the maximum area in a histogram given its heights
public int leetcode84(int[] heights) {
Stack <Integer> stack = new Stack<>();
stack.push(-1);
int maxarea = 0;
for (int i = 0; i < heights.length; ++i) {
while (stack.peek() != -1
&& heights[stack.peek()] >= heights[i]) {
maxarea = Math.max(maxarea, heights[stack.pop()] * (i - stack.peek() - 1));
}
stack.push(i);
}
while (stack.peek() != -1) {
maxarea = Math.max(maxarea, heights[stack.pop()] * (heights.length - stack.peek() - 1));
}
return maxarea;
}
}

### Approach #4 Dynamic Programming - Maximum Height at Each

Complexity Analysis
• Time complexity : O(NM). In each iteration over `N` we iterate over `M` a constant number of times.
• Space complexity : O(M). `M` is the length of the additional arrays we keep.
class Solution {
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]; // initialize left as the leftmost boundary possible
int[] right = new int[n];
int[] height = new int[n];
Arrays.fill(right, n); // initialize right as the rightmost boundary possible
int maxarea = 0;
for (int i = 0; i < m; i++) {
int cur_left = 0, cur_right = n;
// update height
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
height[j]++;
} else {
height[j] = 0;
}
}
// update left
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
left[j] = Math.max(left[j], cur_left);
} else {
left[j] = 0;
cur_left = j + 1;
}
}
// update right
for (int j = n - 1; j >= 0; j--) {
if (matrix[i][j] == '1') {
right[j] = Math.min(right[j], cur_right);
} else {
right[j] = n;
cur_right = j;
}
}
// update area
for (int j = 0; j < n; j++) {
maxarea = Math.max(maxarea, (right[j] - left[j]) * height[j]);
}
}
return maxarea;
}
}
/*
j:0 left:0 right:1 height:1
j:1 left:0 right:5 height:0
j:2 left:2 right:3 height:1
j:3 left:0 right:5 height:0
j:4 left:0 right:5 height:0
j:0 left:0 right:1 height:2
j:1 left:0 right:5 height:0
j:2 left:2 right:3 height:2
j:3 left:2 right:5 height:1
j:4 left:2 right:5 height:1
j:0 left:0 right:1 height:3
j:1 left:0 right:5 height:1
j:2 left:2 right:3 height:3
j:3 left:2 right:5 height:2
j:4 left:2 right:5 height:2
j:0 left:0 right:1 height:4
j:1 left:0 right:5 height:0
j:2 left:0 right:5 height:0
j:3 left:3 right:4 height:3
j:4 left:0 right:5 height:0
*/

### Approach #5 Divde and Conquer

`Time: average case: O(n log n) Worst case: O(N^2)` `Space: O(n)`
public class Solution {
public int largestRectangleArea(int[] heights) {
return calculateArea(heights, 0, heights.length - 1);
}
public int calculateArea(int[] heights, int start, int end) {
if (start > end)
return 0;
int minindex = start;
for (int i = start; i <= end; i++)
if (heights[minindex] > heights[i])
minindex = i;
return Math.max(heights[minindex] * (end - start + 1), Math.max(calculateArea(heights, start, minindex - 1), calculateArea(heights, minindex + 1, end)));
}
}
Better Divde and Conquer
Using a Segment Tree to find the minimum every time which can be done in `O(log n)` time `Time: average case: O(n log n)` `Space: O(n)`