LeetCode 筆記 - 84. Largest Rectangle in Histogram

Posted on

題目在此 84. Largest Rectangle in Histogram

給定一個整數陣列 heights，其中每個元素代表直方圖中每個柱子的高度，請找出能夠形成的最大矩形面積。

解題思維

這題的關鍵在於，對每一個柱子，找出以它為高度所能畫出的最大矩形。

要做到這點，我們需要知道每個柱子能向左和向右延伸的最大寬度。也就是說，我們要為每個柱子 i 找到它左邊第一個比它矮的柱子 left，以及右邊第一個比它矮的柱子 right。這樣，以 heights[i] 為高的矩形寬度就是 right - left - 1。

「單調堆疊」就是幫助我們在一次遍歷中高效完成這件事的工具。

我們的策略是維護一個高度由底到頂遞增的堆疊（儲存索引）。當我們遍歷到柱子 i 時：

  1. 如果 heights[i] 比堆疊頂端的柱子高，就直接把 i 推入堆疊，維持遞增的特性。
  2. 如果 heights[i] 比堆疊頂端的柱子矮，這就是一個關鍵時刻！這代表我們找到了堆疊頂端柱子的「右邊界」（就是 i）。

此時，我們就可以開始計算面積：

  1. 將堆疊頂端的索引 h_idx 彈出，矩形高度就是 heights[h_idx]。
  2. h_idx 的右邊界是 i。
  3. h_idx 的左邊界則是彈出後，堆疊中新的頂端元素。

我們重複這個彈出和計算的過程，直到堆疊頂端的柱子不再比 heights[i] 高，然後才將 i 推入堆疊。

Time complexity 是 $O(n)$，因為每個元素最多只會被放入和彈出堆疊一次。
Space complexity 是 $O(n)$，因為在最壞情況下，堆疊中可能會包含所有的元素。

程式碼

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
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:

        # step 0: use stack, keep the elements in stack is increased.
        # step 1: in ith, if the current height is smaller than stack[-1]
        #.        It means i is the right side of area,
        #         the height of area is stack[-1], so we pop it as height
        #         the left side is the new stack[-1]
        #         current area = right - left - 1 (include left), keep the result is max(result, cur_area)
        # step 2: stack.append(i), it means i is the new min height form left side.

        # time complexity: O(n)
        # space complexity: O(n)
        
        heights.append(0)
        stack = [-1]

        result = 0

        for i in range(len(heights)):

            h = heights[i]

            while heights[stack[-1]] > h:
                # h is rigth side

                h_idx = stack.pop()

                left = stack[-1]
                right = i

                width = right - left - 1

                cur_area = heights[h_idx] * width

                result = max(result, cur_area)

            stack.append(i)

        return result

也許你也會想看看