Maximal Rectangle
给一个2d数组, 里面是0和1. 返回最大的全是1的矩形. 这个题和柱状图的最大矩形是一个解法.用largest方法找到一个数组上最大的矩形.
|
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 36 37 |
public class Solution { public int maximalRectangle(char[][] matrix) { if(matrix == null || matrix.length == 0) return 0; int[] hist = new int[matrix[0].length]; int m = matrix.length; int n = matrix[0].length; int max = 0; for(int i = 0 ; i < m; i++) { for(int j = 0 ; j < n; j++) { if(matrix[i][j] == '1') hist[j] ++; else hist[j] = 0; } max = Math.max(max, largest(hist)); } return max; } public int largest(int[] height) { if(height == null || height.length == 0) return 0; int max = 0; Stack<Integer> st = new Stack<Integer>(); for(int i = 0 ; i <= height.length; i++) { int cur = (i == height.length)? 0:height[i]; if(st.empty() || cur > height[st.peek()]) st.push(i); else{ int tmp = st.pop(); max = Math.max(max, height[tmp] *(st.empty()? i : i - st.peek() - 1) ); i--; } } return max; } } |