首页 > 代码库 > 85. Maximal Rectangle
85. Maximal Rectangle
Given a 2D binary matrix filled with 0‘s and 1‘s, find the largest rectangle containing only 1‘s and return its area.
For example, given the following matrix:
1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0
Return 6.
【题目分析】
【思路】
【java代码】
1 public class Solution { 2 public int maximalRectangle(char[][] matrix) { 3 int row = matrix.length; 4 if(row == 0) return 0; 5 int col = matrix[0].length; 6 if(col == 0) return 0; 7 8 int maxArea = 0; 9 10 for(int i = 0; i < row; i++){11 int[] height = new int[col];12 for(int j = 0; j < col; j++){13 if(matrix[i][j] == ‘1‘){14 for(int k = i; k >=0; k--){15 if(matrix[k][j] == ‘1‘){16 height[j]++;17 }18 else break;19 }20 }21 }22 maxArea = Math.max(maxArea, largestRectangleArea(height));23 }24 25 return maxArea;26 }27 28 public int largestRectangleArea(int[] height) {29 int len = height.length;30 Stack<Integer> s = new Stack<Integer>();31 int maxArea = 0;32 for(int i = 0; i <= len; i++){33 int h = (i == len ? 0 : height[i]);34 if(s.isEmpty() || h >= height[s.peek()]){35 s.push(i);36 }else{37 int tp = s.pop();38 maxArea = Math.max(maxArea, height[tp] * (s.isEmpty() ? i : i - 1 - s.peek()));39 i--;40 }41 }42 return maxArea;43 }44 }
85. Maximal Rectangle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。