85.Maximal Rectangle
发布时间:2020-12-14 04:15:58 所属栏目:大数据 来源:网络整理
导读:Given a 2D binary matrix filled with 0‘s and 1‘s,find the largest rectangle containing only 1‘s and return its area. Example:Input:[ [ "1","0","1","0" ],[ "1","1" ],"0" ]]Output: 6 https: // www.youtube.com/watch?v=2Yk3Avrzaukt=450s cla
Given a 2D binary matrix filled with 0‘s and 1‘s,find the largest rectangle containing only 1‘s and return its area. Example: Input: [ ["1","0","1","0"],["1","1"],"0"] ] Output: 6 https://www.youtube.com/watch?v=2Yk3Avrzauk&t=450s class Solution { public int maximalRectangle(char[][] matrix) { if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0; int row = matrix.length; int col = matrix[0].length; int[] height = new int[col]; int max = 0; for(int i = 0; i < row; i++){ for(int j = 0; j < col; j++){ if(matrix[i][j] == ‘1‘){ height[j]++; }else{ height[j] = 0; } } int area = largestArea(height); max = Math.max(area,max); } return max; } private int largestArea(int[] height){ int len = height.length; Stack<Integer> s = new Stack<Integer>(); int maxArea = 0; for(int i = 0; i <= len; i++){ int h = (i == len ? 0 : height[i]); if(s.isEmpty() || h >= height[s.peek()]){ s.push(i); }else{ int tp = s.pop(); maxArea = Math.max(maxArea,height[tp] * (s.isEmpty() ? i : i - 1 - s.peek())); i--; } } return maxArea; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |