[LeetCode] 85. Maximal Rectangle

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

Example 2:

Input: matrix = []
Output: 0

Example 3:

Input: matrix = [["0"]]
Output: 0

Example 4:

Input: matrix = [["1"]]
Output: 1

Example 5:

Input: matrix = [["0","0"]]
Output: 0

Constraints:

rows == matrix.length
cols == matrix.length
0 <= row, cols <= 200
matrix[i][j] is '0' or '1'.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

最大矩形。

题意是给一个二维矩阵，求二维矩阵里面由1组成的最大矩形的面积是什么。这个题有DP和单调栈两种做法，我这里给出单调栈的解法。思路跟84题类似，你可以把每一行想象成84题的bars，跑一下例子，比如我们从最后一行往上遍历，最后一行是

[1, 0, 0, 1, 0]

按照84题的思路，能组成的最大的矩形面积是1；

接着把倒数第二行的数字叠加进来，叠加的思路是，若下一行相同位置上为0，则当前位置是1；若下一行相同位置上不为0，则当前位置 + 1。

[1, 1, 1, 1, 1]

[1, 0, 0, 1, 0]

得到

[2, 1, 1, 2, 1]

从而得到最大矩形面积是2。以此类推可以得到这个4*5的矩阵里面最大的矩形的面积。

时间O(mn)

空间O(n)

Java实现

 1 class Solution {
 2     public int maximalRectangle(char[][] matrix) {
 3         // corner case
 4         if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
 5             return 0;
 6         }
 7 
 8         // normal case
 9         int row = matrix.length;
10         int col = matrix[0].length;
11         int[] heights = new int[col];
12         int max = 0;
13         for (int i = 0; i < row; i++) {
14             for (int j = 0; j < col; j++) {
15                 if (matrix[i][j] == '1') {
16                     heights[j]++;
17                 } else {
18                     heights[j] = 0;
19                 }
20             }
21             int area = helper(heights);
22             max = Math.max(max, area);
23         }
24         return max;
25     }
26 
27     private int helper(int[] heights) {
28         if (heights == null || heights.length == 0) {
29             return 0;
30         }
31         Stack<Integer> stack = new Stack<>();
32         int res = 0;
33         for (int i = 0; i <= heights.length; i++) {
34             int cur = i == heights.length ? 0 : heights[i];
35             while (!stack.isEmpty() && cur < heights[stack.peek()]) {
36                 int height = heights[stack.pop()];
37                 int start = stack.isEmpty() ? -1 : stack.peek();
38                 int area = height * (i - start - 1);
39                 res = Math.max(res, area);
40             }
41             stack.push(i);
42         }
43         return res;
44     }
45 }

JavaScript实现

 1 /**
 2  * @param {character[][]} matrix
 3  * @return {number}
 4  */
 5 var maximalRectangle = function(matrix) {
 6     // corner case
 7     if (matrix == null || matrix.length == 0) {
 8         return 0;
 9     }
10 
11     // normal case
12     let res = 0;
13     let row = matrix.length;
14     let col = matrix[0].length;
15     let heights = new Array(col).fill(0);
16     for (let i = 0; i < row; i++) {
17         for (let j = 0; j < col; j++) {
18             if (matrix[i][j] == '1') {
19                 heights[j]++;
20             } else {
21                 heights[j] = 0;
22             }
23         }
24         let area = helper(heights);
25         res = Math.max(res, area);
26     }
27     return res;
28 };
29 
30 var helper = function(heights) {
31     // corner case
32     if (heights == null || heights.length == 0) {
33         return 0;
34     }
35 
36     // normal case
37     let stack = [];
38     let res = 0;
39     for (let i = 0; i <= heights.length; i++) {
40         let h = i == heights.length ? 0 : heights[i];
41         while (stack.length && h < heights[stack[stack.length - 1]]) {
42             let height = heights[stack.pop()];
43             let start = !stack.length ? -1 : stack[stack.length - 1];
44             let area = height * (i - start - 1);
45             res = Math.max(res, area);
46         }
47         stack.push(i);
48     }
49     return res;
50 };