LeetCode 筆記 - 84. Largest Rectangle in Histogram
題目在此 84. Largest Rectangle in Histogram
給定一個整數陣列 heights,其中每個元素代表直方圖中每個柱子的高度,請找出能夠形成的最大矩形面積。
解題思維
這題的關鍵在於,對每一個柱子,找出以它為高度所能畫出的最大矩形。
要做到這點,我們需要知道每個柱子能向左和向右延伸的最大寬度。也就是說,我們要為每個柱子 i 找到它左邊第一個比它矮的柱子 left,以及右邊第一個比它矮的柱子 right。這樣,以 heights[i] 為高的矩形寬度就是 right - left - 1。
「單調堆疊」就是幫助我們在一次遍歷中高效完成這件事的工具。
我們的策略是維護一個高度由底到頂遞增的堆疊(儲存索引)。當我們遍歷到柱子 i 時:
- 如果
heights[i]比堆疊頂端的柱子高,就直接把i推入堆疊,維持遞增的特性。 - 如果
heights[i]比堆疊頂端的柱子矮,這就是一個關鍵時刻!這代表我們找到了堆疊頂端柱子的「右邊界」(就是i)。
此時,我們就可以開始計算面積:
- 將堆疊頂端的索引
h_idx彈出,矩形高度就是heights[h_idx]。 h_idx的右邊界是i。h_idx的左邊界則是彈出後,堆疊中新的頂端元素。
我們重複這個彈出和計算的過程,直到堆疊頂端的柱子不再比 heights[i] 高,然後才將 i 推入堆疊。
Time complexity 是 $O(n)$,因為每個元素最多只會被放入和彈出堆疊一次。
Space complexity 是 $O(n)$,因為在最壞情況下,堆疊中可能會包含所有的元素。
程式碼
1 | class Solution: |