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 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 6.
【题目分析】
这个问题是要在一个0-1矩阵中找到由1构成的最大最大的矩阵的面积。
【思路】
如何下手呢？
我们把这个问题转换成之前已经解决过的问题，Largest Rectangle in Histogram。
对于每一行数据，如果该位置是1，则我们可以向上延伸找到该位置对应的一个height，处理完一行数据后可以得到一个高度行向量。例如题目中矩阵的
第二行对应的向量如下：
第三行对应的向量如下：
第四行对应的向量如下：
这样我们就把这个问题转换成了多个Largest Rectangle in Histogram问题，问题很容易就解决了。
【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 } 转载于:https://www.cnblogs.com/liujinhong/p/5883193.html