【LeetCode日記】84. 柱狀圖中最大的矩形
- 2020 年 3 月 12 日
- 筆記
題目描述
` 給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。
求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。
以上是柱狀圖的示例，其中每個柱子的寬度為 1，給定的高度為 [2,1,5,6,2,3]。
圖中陰影部分為所能勾勒出的最大矩形面積，其面積為 10 個單位。
示例：
輸入：[2,1,5,6,2,3] 輸出：10
暴力枚舉 – 左右端點法（TLE）
思路
我們暴力嘗試所有可能的矩形。由於矩陣是二維圖形， 我我們可以使用左右兩個端點來唯一確認一個矩陣。因此我們使用雙層循環枚舉所有的可能性即可。而矩形的面積等於（右端點坐標 - 左端點坐標 + 1) * 最小的高度，最小的高度我們可以在遍歷的時候順便求出。
程式碼
class Solution: def largestRectangleArea(self, heights: List[int]) -> int: n, ans = len(heights), 0 if n != 0: ans = heights[0] for i in range(n): height = heights[i] for j in range(i, n): height = min(height, heights[j]) ans = max(ans, (j - i + 1) * height) return ans
複雜度分析
- 時間複雜度：
- 空間複雜度：
暴力枚舉 – 中心擴展法（TLE）
思路
我們仍然暴力嘗試所有可能的矩形。只不過我們這一次從中心向兩邊進行擴展。對於每一個 i，我們計算出其左邊第一個高度小於它的索引 p，同樣地，計算出右邊第一個高度小於它的索引 q。那麼以 i 為最低點能夠構成的面積就是(q - p - 1) * heights[i]。這種演算法毫無疑問也是正確的。我們證明一下，假設 f(i) 表示求以 i 為最低點的情況下，所能形成的最大矩陣面積。那麼原問題轉化為max(f(0), f(1), f(2), ..., f(n - 1))。
具體演算法如下：
- 我們使用 l 和 r 數組。l[i] 表示 左邊第一個高度小於它的索引，r[i] 表示 右邊第一個高度小於它的索引。
- 我們從前往後求出 l，再從後往前計算出 r。
- 再次遍歷求出所有的可能面積，並取出最大的。
程式碼
class Solution: def largestRectangleArea(self, heights: List[int]) -> int: n = len(heights) l, r, ans = [-1] * n, [n] * n, 0 for i in range(1, n): j = i - 1 while j >= 0 and heights[j] >= heights[i]: j -= 1 l[i] = j for i in range(n - 2, -1, -1): j = i + 1 while j < n and heights[j] >= heights[i]: j += 1 r[i] = j for i in range(n): ans = max(ans, heights[i] * (r[i] - l[i] - 1)) return ans
複雜度分析
- 時間複雜度：
- 空間複雜度：
優化中心擴展法（Accepted）
思路
實際上我們內層循環沒必要一步一步移動，我們可以直接將j -= 1 改成 j = l[j], j += 1 改成 j = r[j]。
程式碼
class Solution: def largestRectangleArea(self, heights: List[int]) -> int: n = len(heights) l, r, ans = [-1] * n, [n] * n, 0 for i in range(1, n): j = i - 1 while j >= 0 and heights[j] >= heights[i]: j = l[j] l[i] = j for i in range(n - 2, -1, -1): j = i + 1 while j < n and heights[j] >= heights[i]: j = r[j] r[i] = j for i in range(n): ans = max(ans, heights[i] * (r[i] - l[i] - 1)) return ans
複雜度分析
- 時間複雜度：
- 空間複雜度：
單調棧（Accepted）
思路
實際上，讀完第二種方法的時候，你應該注意到了。我們的核心是求左邊第一個比 i 小的和右邊第一個比 i 小的。如果你熟悉單調棧的話，那麼應該會想到這是非常適合使用單調棧來處理的場景。
為了簡單起見，我在 heights 首尾添加了兩個哨兵元素，這樣可以減少邊界處理的額外程式碼。
程式碼
class Solution: def largestRectangleArea(self, heights: List[int]) -> int: n, heights, st, ans = len(heights), [0] + heights + [0], [], 0 for i in range(n + 2): while st and heights[st[-1]] > heights[i]: ans = max(ans, heights[st.pop(-1)] * (i - st[-1] - 1)) st.append(i) return ans
複雜度分析
- 時間複雜度：
- 空間複雜度：
