首页 > 代码库 > Maximal Rectangle

Maximal Rectangle

2024-07-10 21:31:42   229人阅读

Given a 2D binary matrix filled with 0‘s and 1‘s, find the largest rectangle containing all ones and return its area.

用动态规划去做，用grid[i]记录matrix[][i]向下有多少个连续的1，就转化为求n个直方图最大面积的问题，求出最大值，计算每行的grid数组时间复杂度为O(n),再求该数组直方图最大面积的时间复杂度为O(n)。共有n行，则总体时间复杂度为O(n^2)。

求矩阵直方图的做法参见Trapping Rain Water。

本题代码如下：

 1 public int maximalRectangle(char[][] matrix) { 2         if(matrix==null||matrix.length==0){ 3             return 0; 4         } 5         int[] grid= new int[matrix[0].length]; 6         int max = 0; 7         for(int i=matrix.length-1;i>=0;i--){ 8             for(int j=0;j<matrix[0].length;j++){ 9                 if(i==matrix.length-1){10                     grid[j] = (matrix[i][j]==‘1‘?1:0);11                 }else{12                     grid[j] = (matrix[i][j]==‘1‘?1+grid[j]:0);13                 }14             }15             Stack<Integer> pos = new Stack<>();16             Stack<Integer> high = new Stack<>();17             int m = 0;18             pos.add(0);19             high.add(grid[0]);20             for(int k=1;k<grid.length;k++){21                 int p = k;22                 while(!high.empty()&&grid[k]<high.peek()){23                     p = pos.pop();24                     int area = (k-p)*high.pop();25                     m = m>area?m:area;26                 }27                 pos.add(p);28                 high.add(grid[k]);29             }30             while(!high.empty()){31                 int area = (grid.length-pos.pop())*high.pop();32                 m = m>area?m:area;33             }34             max=max>m?max:m;35         }36         return max;37     }


联系
我们