1+ // 85. 最大矩形
2+
3+
4+ /*
5+ 暴力破解/动态规划：
6+ 1、思路：遍历每个点，求以这个点为矩形右下角的所有矩形面积，比较并记录最大面积
7+ 2、二维数组width用于记录每行上每个点结尾的连续 1 的个数，即每行上每个点结尾时的宽度。width可以理解为dp数组，保存状态
8+ 3、从左到右遍历，计算并记录每行上每个点结尾时的宽度
9+ 4、计算面积
10+ 1）首先求出高度是 1 的矩形面积，即高度只有一行，宽度是该点记录的宽度
11+ 2）然后向上扩展一行，高度增加1，选出width当前列最小的数字，即多行的宽度选择最小的宽度为有效宽度，作为矩形的宽度，求出面积
12+ 3）然后继续向上扩展，重复步骤 2，求出所有可能的高度时的面积
13+ */
14+ class Solution {
15+ public int maximalRectangle (char [][] matrix ) {
16+ int m = matrix .length , n = matrix [0 ].length ;
17+ int maxArea = 0 ;
18+ int [][] width = new int [m ][n ];
19+ for (int row = 0 ; row < m ; row ++) {
20+ for (int col = 0 ; col < n ; col ++) {
21+ if (matrix [row ][col ] == '1' ) {
22+ width [row ][col ] = col == 0 ? 1 : width [row ][col - 1 ] + 1 ;
23+ }
24+ int midWidth = width [row ][col ];
25+ for (int rowUp = row ; rowUp >= 0 ; rowUp --) {
26+ int height = row - rowUp + 1 ;
27+ midWidth = Math .min (midWidth , width [rowUp ][col ]);
28+ maxArea = Math .max (maxArea , midWidth * height );
29+ }
30+ }
31+ }
32+ return maxArea ;
33+ }
34+ }
35+
36+
37+ /*
38+ 暴力破解：
39+ 1、遍历每一行的时候，从上往下计算每一列连续1的个数作为矩形高度，得到高度矩阵
40+ 2、遍历高度矩阵，以当前点的值作为矩形高度，向左右两边扩展高度大于等于当前高度的边界得到宽度，从而计算该点的最大面积
41+ 3、比较并记录矩阵所有点的最大面积，得出整个矩阵的最大面积
42+ */
43+ class Solution {
44+ public int maximalRectangle (char [][] matrix ) {
45+ int m = matrix .length , n = matrix [0 ].length ;
46+ int [][] heights = new int [m ][n ];
47+ int maxArea = 0 ;
48+ for (int col = 0 ; col < n ; col ++) {
49+ heights [0 ][col ] = matrix [0 ][col ] == '1' ? 1 : 0 ;
50+ }
51+ for (int row = 1 ; row < m ; row ++) {
52+ for (int col = 0 ; col < n ; col ++) {
53+ if (matrix [row ][col ] == '1' ) {
54+ heights [row ][col ] = heights [row - 1 ][col ] + 1 ;
55+ }
56+ }
57+ }
58+ for (int row = 0 ; row < m ; row ++) {
59+ for (int col = 0 ; col < n ; col ++) {
60+ if (heights [row ][col ] == 0 || heights [row ][col ] * n <= maxArea ) {
61+ continue ;
62+ }
63+ int width = 1 ;
64+ for (int k = col - 1 ; k >= 0 ; k --) {
65+ if (heights [row ][k ] < heights [row ][col ]) {
66+ break ;
67+ }
68+ width ++;
69+ }
70+ for (int k = col + 1 ; k < n ; k ++) {
71+ if (heights [row ][k ] < heights [row ][col ]) {
72+ break ;
73+ }
74+ width ++;
75+ }
76+ maxArea = Math .max (maxArea , width * heights [row ][col ]);
77+ }
78+ }
79+ return maxArea ;
80+ }
81+ }
82+
83+
84+ /*
85+ 单调递增栈：
86+ 1、遍历每一行的时候，从上往下计算每一列连续1的个数作为矩形高度，得到高度数组
87+ 2、直接利用“84. 柱状图中最大的矩形”的解法，传入高度数组，得到最大矩形面积
88+ 3、在所有行的矩形面积结果中，记录最大面积
89+ */
90+ class Solution {
91+ public int maximalRectangle (char [][] matrix ) {
92+ int m = matrix .length , n = matrix [0 ].length ;
93+ int [] heights = new int [n ];
94+ int maxArea = 0 ;
95+ for (int row = 0 ; row < m ; row ++) {
96+ for (int col = 0 ; col < n ; col ++) {
97+ if (matrix [row ][col ] == '1' ) {
98+ heights [col ] += 1 ;
99+ } else {
100+ heights [col ] = 0 ;
101+ }
102+ }
103+ maxArea = Math .max (maxArea , largestRectangleArea (heights ));
104+ }
105+ return maxArea ;
106+ }
107+
108+ private int largestRectangleArea (int [] heights ) {
109+ int res = 0 ;
110+ int n = heights .length ;
111+ int [] newHeights = new int [n + 2 ];
112+ System .arraycopy (heights , 0 , newHeights , 1 , n );
113+ Deque <Integer > stack = new ArrayDeque <>();
114+ for (int right = 0 ; right < n + 2 ; right ++) {
115+ while (!stack .isEmpty () && newHeights [right ] < newHeights [stack .peek ()]) {
116+ int cur = stack .pop ();
117+ int left = stack .peek ();
118+ int area = (right - left - 1 ) * newHeights [cur ];
119+ res = Math .max (res , area );
120+ }
121+ stack .push (right );
122+ }
123+ return res ;
124+ }
125+ }
0 commit comments