[leetcode]Maximal Rectangle

这题也是做一次想一次

其实就是base on largest rectangle in histogram的idea

从上到下 把每行当作histogram的地基 再生成对应高度 然后交给largest rectangle去算面积

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

public class Solution { public int maximalRectangle(char[][] matrix) { if (matrix == null || matrix.length == 0) return 0; int []rolling = new int[matrix[0].length+1]; int maxArea = 0; for (int i = 0; i < matrix.length; i++){ for (int j = 0; j < matrix[i].length; j++){ rolling[j] = matrix[i][j] == '0'?0:rolling[j]+1; } maxArea = Math.max(maxArea, findLargest(rolling)); } return maxArea; } private int findLargest(int []height){ Stack<Integer> stack = new Stack<Integer>(); int max = 0; for (int i = 0; i < height.length; i++){ while (!stack.isEmpty() && height[i] < height[stack.peek()]){ int index = stack.pop(); int width = i-(stack.isEmpty()?0:(stack.peek()+1)); max = Math.max(max, height[index]*width); } stack.push(i); } return max; } }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

public class Solution { public int maximalRectangle(char[][] matrix) { if (matrix == null || matrix.length == 0){ return 0; } int rolling[] = new int[matrix[0].length]; int maxArea = 0; for (int i = 0; i < matrix.length; i++){ for (int j = 0; j < matrix[i].length; j++){ rolling[j] = (matrix[i][j] == '0'?0:rolling[j]+1); } maxArea = Math.max(maxArea, maxAreaHistogram(rolling)); } return maxArea; } public int maxAreaHistogram(int histogram[]){ if (histogram == null){ return 0; } Stack<Integer> stack = new Stack<Integer>(); int dummyHis[] = Arrays.copyOf(histogram, histogram.length+1); int i = 0; int maxArea = 0; while (i < dummyHis.length){ if (stack.isEmpty() || dummyHis[i] >= dummyHis[stack.peek().intValue()]){ stack.push(i++); }else{ int temp = stack.pop().intValue(); maxArea = Math.max(maxArea, dummyHis[temp]*(stack.isEmpty()?i:i-stack.peek().intValue()-1)); } } return maxArea; } }