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