Let's look at the reason.
In this small example, we can assume each row as a histogram with each bar at the corresponding height. Then we calculate the maximum of all these maximum rectangles, then, problem solved!
public class MaxRectangle { public int maximalRectangle(char[][] matrix) { if (matrix == null || matrix.length == 0) return 0; int m = matrix.length; int n = matrix[0].length; int[][] height = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (matrix[i][j] == '0') height[i][j] = 0; else { height[i][j] = (i == 0) ? 1 : height[i - 1][j] + 1; } } } int maxArea = 0; for (int i = 0; i < m; i++) maxArea = Math.max(maxArea, getArea(height[i])); return maxArea; } private int getArea(int[] height) { Stackstack = new Stack (); int maxArea = 0; for (int i = 0; i <= height.length; i++) { int curr = (i == height.length) ? -1 : height[i]; while (!stack.isEmpty() && curr <= height[stack.peek()]) { int h = height[stack.pop()]; int w = stack.isEmpty() ? i : i - stack.peek() - 1; maxArea = Math.max(maxArea, h * w); } stack.push(i); } return maxArea; } }
No comments:
Post a Comment