首页 > 代码库 > 【leetcode刷题笔记】Maximal Rectangle

【leetcode刷题笔记】Maximal Rectangle

2024-07-13 22:36:06   226人阅读

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

 

题解，很巧妙的一道题，对于一个0-1矩阵，它的每一行及以上都可以看作一个直方图（如下图所示），利用Largest Rectangle in Histogram的方法，可以在O(n)的时间搜索出这一行及以上的直方图中面积最大的矩形，对矩阵的每一行依次做这个操作，就可以在O(n2)的时间搜索出最大的矩形了。

将原矩阵转换成直方图矩阵的方法：设用transfer矩阵存放转换后的直方图，则

transfer[0][j] = matrix[0][j] - ‘0‘;transfer[i][j] = (matrix[i][j] == ‘0‘ ? 0: transfer[i-1][j] + 1); (i >= 1)

代码如下：

 1 public class Solution { 2     public int largestRectangleArea(int[] height) { 3         if(height == null || height.length == 0) 4             return 0; 5         Stack<Integer> index = new Stack<Integer>(); 6         int totalMax = 0; 7         ArrayList<Integer> newHeight = new ArrayList<Integer>(); 8         for(int i:height) newHeight.add(i); 9         newHeight.add(0);10         11         12         for(int i = 0;i < newHeight.size();i++){13             if(index.isEmpty() || newHeight.get(i) >= newHeight.get(index.peek()))14                 index.push(i);15             else{16                 int top = index.pop();17                 totalMax = Math.max(totalMax,newHeight.get(top) * (index.isEmpty()?i:i-index.peek()-1));18                 i--;19             }20         }21         22         return totalMax;23     }24     public int maximalRectangle(char[][] matrix) {25         if(matrix == null || matrix.length == 0)26             return 0;27         int m = matrix.length;28         int n = matrix[0].length;29         int totalMax = 0;30         int[][] transfer = new int[m][n];31         32         //transform matrix to histogram in a new matrix33         for(int i = 0;i < n;i++)34             transfer[0][i] = matrix[0][i]- ‘0‘;35         for(int i = 1;i < m;i++){36             for(int j = 0;j < n;j++){37                 if(matrix[i][j] == ‘0‘ )38                     transfer[i][j] = 0;39                 else {40                     transfer[i][j] = transfer[i-1][j] + 1; 41                 }42             }43         }44         45         //Using histogram to find the biggest rectangle46         for(int i = 0;i < m;i++){47             totalMax = Math.max(totalMax, largestRectangleArea(transfer[i]));48         }49         50         return totalMax;51     }52 }


联系
我们