Algorithm - LeetCode 84 - Largest Rectangle in Histogram
Description
Sample
input
heights = [2,1,5,6,2,3]
output
10
Key points
- 目標是 找到每個柱子能擴展的最大寬度，然後計算以該柱子為高度的最大矩形面積。
Solution 1 - 暴力解
- 對於每個
heights[i]，向 左、右 擴展，直到遇到比它矮的柱子。 - 左邊界 (left)：找第一個小於 heights[i] 的索引
- 右邊界 (right)：找第一個小於 heights[i] 的索引
- 寬度 (width)：
width = right - left - 1 - 面積 (area)：
area = heights[i] * (right - left - 1)
推導
| i | heights[i] | left | right | width | area |
|---|---|---|---|---|---|
| 0 | 2 | -1 | 1 | 1 | 2 |
| 1 | 1 | -1 | 6 | 6 | 6 |
| 2 | 5 | 1 | 4 | 2 | 10 |
| 3 | 6 | 2 | 4 | 1 | 6 |
| 4 | 2 | 1 | 6 | 4 | 8 |
| 5 | 3 | 4 | 6 | 1 | 3 |
最大矩形面積 = 10
複雜度
- 時間複雜度：O(n^2)
- 空間複雜度：O(n)
Solution 2 - 單調棧
單調棧 : 棧內元素 會按照 遞增/減順序 存放
- 使用 單調遞增棧（Monotonic Increasing Stack）
- 當 遇到一個比棧頂元素小的數，意味著 棧頂柱子找到了右邊界
- 右邊界確定時，順便出棧，並計算面積
推導
- 設定
stack = [] - 為了確保最後能計算所有矩形，在 heights 末尾補 0，確保最後所有柱子都會出棧。
| i | heights[i] | Stack (i) | action | area |
|---|---|---|---|---|
| 0 | 2 | [0] | 入棧 | |
| 1 | 1 | [] | 出棧 (2 找到右邊界) | 2 * (1 - 0) = 2 |
| 1 | 1 | [1] | 入棧 | |
| 2 | 5 | [1,2] | 入棧 | |
| 3 | 6 | [1,2,3] | 入棧 | |
| 4 | 2 | [1,2] | 出棧 (6 找到右邊界) | 6 * (4 - 3) = 6 |
| 4 | 2 | [1] | 出棧 (5 找到右邊界) | 5 * (4 - 2) = 10 |
| 4 | 2 | [1,4] | 入棧 | |
| 5 | 3 | [1,4,5] | 入棧 | |
| 6 | 0 | [1,4] | 出棧 (3 找到右邊界) | 3 * (6 - 5) = 3 |
| 6 | 0 | [1] | 出棧 (2 找到右邊界) | 2 * (6 - 1) = 8 |
| 6 | 0 | [] | 出棧 (1 找到右邊界) | 1 * (6 - 0) = 6 |
最大矩形面積 = 10
複雜度
- 時間複雜度：O(n)
- 空間複雜度：O(n)