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)
转化成 Leetcode 84 的单调递增栈
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)