Python程式：查詢直方圖中最大矩形面積

假設我們有一列數字，表示直方圖中條形的高度。我們需要找到可以在條形下形成的最大矩形的面積。

因此，如果輸入類似於 nums = [3, 2, 5, 7]

則輸出將為 10

為了解決這個問題，我們將遵循以下步驟：

• stk := 一個棧，最初插入 -1 到其中
• 在heights的末尾插入0
• ans := 0
• 對於 i 從 0 到 heights 的大小，執行：
  • 當 heights[i] < heights[棧頂] 時，執行：
    • h := heights[棧頂] 並從棧中彈出
    • w := i - 棧頂 - 1
    • ans := ans 和 (h * w) 的最大值
  • 將 i 推入棧中
• 返回 ans

讓我們看看下面的實現以更好地理解：

示例

線上演示

class Solution:
   def solve(self, heights):
      stk = [-1]
      heights.append(0)
      ans = 0
      for i in range(len(heights)):
         while heights[i] < heights[stk[-1]]:
            h = heights[stk.pop()]
            w = i - stk[-1] - 1
            ans = max(ans, h * w)
         stk.append(i)
      return ans

ob = Solution()
nums = [3, 2, 5, 7]
print(ob.solve(nums))

輸入

[3, 2, 5, 7]

輸出

10

Arnab Chakraborty

更新於：2020年12月2日

1K+ 次瀏覽

啟動你的職業生涯

透過完成課程獲得認證

開始學習