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
题意：给一个二维数组，算出最大的矩形面积，矩形内部必须全是 1. 这题可以简化成以下两个步骤。 1.求出在一个直方图中，能组合出最大的矩形面积。 2. 以每一行为直方图的bottom，分别算出最大的矩形面积。得出答案。 对于第一个问题，我们可以用单调递增栈来做，因为对每一根柱子来讲，如果求包括当前柱子的最大的面积，我们必须找左右两边比其柱子要小的值。刚好递增栈可以做到。
代码
class Solution {
public int largestRectangleArea(int[] heights) {
if(heights == null || heights.length == 0) return 0;
Stack<Integer> stack = new Stack<>();
int maxArea = 0;
for(int i = 0; i < heights.length; i++) {
while(!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
int j = stack.pop();
int start = stack.isEmpty() ? -1 : stack.peek();
maxArea = Math.max((i - start - 1) * heights[j], maxArea);
}
stack.push(i);
}
while(!stack.isEmpty()) {
int j = stack.pop();
int start = stack.isEmpty() ? -1 : stack.peek();
maxArea = Math.max((heights.length - start - 1) * heights[j], maxArea);
}
return maxArea;
}
public int maximalRectangle(char[][] matrix) {
int max = 0;
if(matrix == null || matrix.length == 0) return 0;
int[] heights = new int[matrix[0].length];
for(int j = 0; j < matrix.length; j++) {
for(int i = 0; i < matrix[0].length; i++) {
heights[i] = matrix[j][i] == '1' ? heights[i] + 1 : 0;
}
max = Math.max(largestRectangleArea(heights), max);
}
return max;
}
}