[LeetCode] 85. Maximal Rectangle

Posted on | In

Problem

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

Example:

1
2
3
4
5
6
7
8
Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

Explanation

  1. We can use 84. Largest Rectangle in Histogram’s solution to solve this problem.

  2. In the input matrix array, we can think of each row is the heights array. For example, the first row is the heights array [1, 0, 1, 0, 0], the second row is the heights array [2, 0, 2, 1, 1], the third row is the array [3, 1, 3, 2, 2], the fourth row is [4, 0, 0, 3, 0]. Then we compute each row’s maximum area by using the 84. Largest Rectangle in Histogram’s function.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    int largestRectangleArea(int[] heights) {
        Stack<Integer> st = new Stack<>();
        int max = 0;
        for (int i = 0; i < heights.length; i++) {
            if (st.isEmpty() || heights[i] > heights[st.peek()]) {
                st.push(i);
            } else {
                int rightMost = i;
                int ind = st.pop();
                while (!st.isEmpty() && st.peek() == ind) {
                    ind = st.pop();
                }
                int leftMost = st.isEmpty() ? -1 : st.peek();
                max = Math.max(max, heights[ind] * (rightMost-leftMost-1));
                i--;
            }
        }
        
        int rightMost = st.peek()+1;
        while (!st.isEmpty()) {
            int ind = st.pop();
            while (!st.isEmpty() && st.peek() == ind) {
                ind = st.pop();
            }
            int leftMost = st.isEmpty() ? -1 : st.peek();
            max = Math.max(max, heights[ind] * (rightMost-leftMost-1));
        }
        
        return max;
    }
    
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int[] heights = new int[matrix[0].length];
        int max = 0;
        
        for (int row = 0; row < matrix.length; row++) {
            for (int col = 0; col < matrix[0].length; col++) {
                if (matrix[row][col] == '0') {
                    heights[col] = 0;
                } else {
                    heights[col] += 1;
                }
            }
            
            int area = largestRectangleArea(heights);
            max = Math.max(max, area);
        }
        
        return max;
    }
}