[LintCode] Maximal Square
|
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 |
public int maxSquare(int[][] matrix) { // write your code here if(matrix == null || matrix.length == 0) return 0; int[] height = new int[matrix[0].length]; int res = 0; for(int i = 0 ; i < matrix.length; i++) { for(int j = 0; j < matrix[0].length; j++) { if(matrix[i][j] == 1) height[j]++; else height[j] = 0; } res = Math.max(res, largest(height)); } return res; } public int largest(int[] height) { if(height == null || height.length == 0) return 0; Stack<Integer> st = new Stack<Integer>(); int max = 0; 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 = (int)Math.max(max, Math.min(height[tmp]*height[tmp], Math.pow((st.empty()? i : i - st.peek()-1),2))); i--; } } return max; } |
Leave A Comment