复用 84. Largest Rectangle in Histogram。
参考这个视频讲解和这个帖子.
Go through the matrix row by row; for each row, record the maximum height each column can reach. Then it becomes a skyline problem, which can be solved in O(n).
class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return 0;
}
int maximalRectangle = 0;
int[] heights = new int[matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == '1') {
heights[j] += 1;
} else {
heights[j] = 0;
}
}
int curMaximal = largestRectangleArea(heights);
maximalRectangle = Math.max(curMaximal, maximalRectangle);
}
return maximalRectangle;
}
public int largestRectangleArea(int[] heights) {
if (heights == null || heights.length == 0) {
return 0;
}
int largestArea = 0;
for (int i = 0; i < heights.length; i++) {
if (i == heights.length - 1 || heights[i] > heights[i + 1]) {
int curHeight = heights[i];
for (int j = i; j >= 0; j --) {
curHeight = Math.min(curHeight, heights[j]);
int curArea = curHeight * (i - j + 1);
largestArea = Math.max(largestArea, curArea);
}
}
}
return largestArea;
}
}