題目描述

` 給定 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

復雜度分析

• 時間復雜度：
• 空間復雜度：

推薦閱讀

1、【算法提高班】《貪婪策略》系列 - 覆蓋篇

2、一個HTTP數據包的奇幻之旅

3、一個函數解決【LeetCode 買賣股票的最佳時機】系列所有題目！

4、原來狀態機也可以用來刷LeetCode？

5、【算法提高班】《我的日程安排表》系列

6、用好這幾個工具，能大幅提升你的 Git/GitHub 操作效率！

如果覺得文章不錯，幫忙點個在看唄

總結

以上是生活随笔為你收集整理的如何给柱状图柱子添加阴影_【LeetCode日记】84. 柱状图中最大的矩形的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。