1+ /*
2+ Author: Andy, nkuwjg@gmail.com
3+ Date: Jan 29, 2015
4+ Problem: Maximal Rectangle
5+ Difficulty: Medium
6+ Source: https://oj.leetcode.com/problems/maximal-rectangle/
7+ Notes:
8+ Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
9+
10+ Solution: 1. dp.
11+ a) dp[i][j] records the number of consecutive '1' on the left and up of the element matrix[i][j].
12+ b) For each element(i,j), calculate the area of rectangle including the element itself.
13+ 2. calculate 'Largest Rectangle in Histogram' for each row.
14+ 3. Time : O(n ^ 2), Space : O(n).
15+ */
16+
17+ public class Solution {
18+ public int maximalRectangle_1 (char [][]matrix ) {
19+ if (matrix .length ==0 ||matrix [0 ].length ==0 )return 0 ;
20+ int M =matrix .length ,N =matrix [0 ].length ;
21+ int [][][]dp =new int [M ][N ][2 ];
22+ int res =0 ;
23+ for (int i =0 ;i <M ; ++i ) {
24+ for (int j =0 ;j <N ; ++j ) {
25+ if (matrix [i ][j ] =='0' )continue ;
26+ dp [i ][j ][0 ] = (j ==0 )?1 :dp [i ][j -1 ][0 ] +1 ;
27+ dp [i ][j ][1 ] = (i ==0 )?1 :dp [i -1 ][j ][1 ] +1 ;
28+ int minheight =dp [i ][j ][1 ];
29+ for (int k =j ;k >j -dp [i ][j ][0 ]; --k ) {
30+ minheight =Math .min (minheight ,dp [i ][k ][1 ]);
31+ res =Math .max (res ,minheight *(j -k +1 ));
32+ }
33+ }
34+ }
35+ return res ;
36+ }
37+ public int cal (int []dp ) {
38+ int N =dp .length ;
39+ Stack <Integer >stk =new Stack <Integer >();
40+ int i =0 ,res =0 ;
41+ while (i <N ) {
42+ if (stk .empty () ||dp [i ] >=dp [stk .peek ()]) {
43+ stk .push (i ++);
44+ continue ;
45+ }
46+ int idx =stk .pop ();
47+ int width =stk .empty ()?i :(i -stk .peek ()-1 );
48+ res =Math .max (res ,width *dp [idx ]);
49+ }
50+ return res ;
51+ }
52+ public int maximalRectangle_2 (char [][]matrix ) {
53+ if (matrix .length ==0 ||matrix [0 ].length ==0 )return 0 ;
54+ int M =matrix .length ,N =matrix [0 ].length ;
55+ int []dp =new int [N +1 ];
56+ int res =0 ;
57+ for (int i =0 ;i <M ; ++i ) {
58+ for (int j =0 ;j <N ; ++j ) {
59+ if (matrix [i ][j ] =='0' )dp [j ] =0 ;
60+ else dp [j ] =dp [j ] +1 ;
61+ }
62+ res =Math .max (res ,cal (dp ));
63+ }
64+ return res ;
65+ }
66+ public int maximalRectangle (char [][]matrix ) {
67+ if (matrix .length ==0 ||matrix [0 ].length ==0 )return 0 ;
68+ int M =matrix .length ,N =matrix [0 ].length ;
69+ int []L =new int [N ];Arrays .fill (L ,0 );
70+ int []R =new int [N ];Arrays .fill (R ,N );
71+ int []H =new int [N ];Arrays .fill (H ,0 );
72+ int res =0 ;
73+ for (int i =0 ;i <M ; ++i ) {
74+ int left =0 ,right =N ;
75+ for (int j =0 ;j <N ; ++j ) {
76+ if (matrix [i ][j ] =='1' ) {
77+ L [j ] =Math .max (L [j ],left );
78+ H [j ] =H [j ] +1 ;
79+ }else {
80+ H [j ] =0 ;L [j ] =0 ;R [j ] =N ;
81+ left =j +1 ;
82+ }
83+ }
84+ for (int j =N -1 ;j >=0 ; --j ) {
85+ if (matrix [i ][j ] =='1' ) {
86+ R [j ] =Math .min (R [j ],right );
87+ res =Math .max (res , (R [j ]-L [j ])*H [j ]);
88+ }else {
89+ right =j ;
90+ }
91+ }
92+ }
93+ return res ;
94+ }
95+ }
