85. Maximal Rectangle (Hard)
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: 6
Solutions
public class Solution {
// This problem is pretty complicated and similar with 84. Largest Rectangle in Histogram. But
// the former is more complicated. You need to calculate the histogram bar by yourself and
// as for problem 84, this information is given by problem.
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[] heights = new int[cLen + 1];
Arrays.fill(heights, 0);
int max = 0;
for (int i = 0; i < rLen; i++) {
// used to keep increasing heights
Stack<Integer> stack = new Stack<>();
for (int j = 0; j < cLen + 1; j++) {
// The quantity of consecutive 1s in same column counting from current row to above
if (j < cLen && matrix[i][j] == '1') {
heights[j] += 1;
}
// 0 cut off the continuity of 1s in same column
if (j < cLen && matrix[i][j] == '0') {
heights[j] = 0;
}
// do not push in less taller height
if (stack.isEmpty() || heights[stack.peek()] <= heights[j]) {
stack.push(j);
continue;
}
while (!stack.isEmpty() && heights[stack.peek()] > heights[j]) {
int height = heights[stack.pop()];
int width = stack.isEmpty() ? j : (j - 1 - stack.peek());
int area = height * width;
max = Math.max(max, area);
}
stack.push(j);
}
}
return max;
}
}