LeetCode 筆記 - 85. Maximal Rectangle

Posted on

題目在此 85. Maximal Rectangle

給定一個 由 0 和 1 組成的二維矩陣，請找出其中只包含 1 的最大矩形，並返回其面積。

85. Maximal Rectangle

解題思維

這題可以拆解成多次解決「Find the max rectangle area with heights」的問題，如果沒寫過可以先試試看：
LeetCode 筆記 - 84. Largest Rectangle in Histogram

具體來說，我們可以將每一行視為直方圖的底部，並計算每一列的高度（即連續 1 的數量）。然後，對於每一行，我們使用 單調堆疊 (Monotonic stack) 的方法來計算該行所能形成的最大矩形面積。

Time complexity 是 $O(n \times m)$，因為我們需要對每一行都計算一次最大矩形面積，而每次計算的時間複雜度是 $O(m)$。
Space complexity 是 $O(m)$，因為我們需要一個高度陣列來存每一列的高度。

程式碼

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
54
class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:

        # step 0: we use "find the max rectangle area with heights" algorithm, it also a hard problem 84. Largest Rectangle in Histogram
        #         use the algorithm n times
        # step 1: keep the heights list, in crrent y, the highest rectangle height we can find.
        # step 2: every time finished the scan, we got a new height list. then we run "find the max rectangle area with heights" algorithm
        # step 3: keep result = max(result, current area)
        # step 4: return result

        # time complexity: O(n * m)
        # space comlexity: (n) len(matrix[0])

        y = m = len(matrix)
        x = n = len(matrix[0])

        heights = [0] * x

        result = 0

        for cur_y in range(y):
            for cur_x in range(x):
                if matrix[cur_y][cur_x] == "1":
                    heights[cur_x] += 1
                else:
                    heights[cur_x] = 0

            # Monotonic stack algorithm

            stack = [-1]
            heights.append(0)

            for i in range(len(heights)):
                h = heights[i]

                while heights[stack[-1]] > h:
                    area_right = i

                    pop_idx = stack.pop()
                    area_h = heights[pop_idx]

                    area_left = stack[-1]

                    area = (area_right - area_left - 1) * area_h

                    result = max(result, area)

                stack.append(i)

            heights.pop()

            # Monotonic stack finish

        return result

也許你也會想看看