85 Maximal Rectangle

85. Maximal Rectangle​
1. Question
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
1 0 1 0 0
2
1 0 1 1 1
3
1 1 1 1 1
4
1 0 0 1 0
Copied!
Return 6.
2. Implementation
思路：这题和Largest Rectangle Histogram的做法完全一样，唯一的不同是，那题的输入就是代表不同高度的数组，而这题需要我们根据matrix每行每个列上连续的1的个数，计算出相应的高度。
1
class Solution {
2
    public int maximalRectangle(char[][] matrix) {
3
        if (matrix == null || matrix.length == 0) {
4
            return 0;
5
        }
6
​
7
        Stack<Integer> stack = null;
8
        int area = 0, maxArea = 0;
9
        int m = matrix.length, n = matrix[0].length;
10
​
11
        int[] heights = new int[n + 1];
12
​
13
        for (int i = 0; i < m; i++) {
14
            stack = new Stack<>();
15
​
16
            for (int j = 0; j < n; j++) {
17
                if (matrix[i][j] == '1') {
18
                    heights[j] += 1;
19
                }
20
                else {
21
                    heights[j] = 0;
22
                }
23
            }
24
​
25
            for (int j = 0; j <= n; j++) {
26
                int curHeight = j == n ? -1 : heights[j];
27
​
28
                while (!stack.isEmpty() && heights[stack.peek()] > curHeight) {
29
                    int topIndex = stack.pop();
30
                    area = heights[topIndex] * (stack.isEmpty() ? j : j - stack.peek() - 1);
31
                    maxArea = Math.max(maxArea, area);
32
                }
33
                stack.push(j);
34
            }
35
        }
36
        return maxArea;
37
    }
38
}
Copied!
3. Time & Space Complexity
时间复杂度是O(mn), 空间复杂度O(n)

84 Largest Rectangle in Histogram

150 Evaluate Reverse Polish Notation

Last modified 2yr ago

Copy link

Contents

85. Maximal Rectangle

1. Question

2. Implementation

3. Time & Space Complexity

85. Maximal Rectangle​

1. Question

2. Implementation

3. Time & Space Complexity

85. Maximal Rectangle