資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學Python程式：計算雨水收集總量
假設我們有一個包含n個非負整數的陣列。這些整數代表高度，每個柱的寬度為1，我們需要計算下雨後能夠收集多少雨水。地圖如下所示：
這裡可以看到有8個藍色方塊，所以輸出為8。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個棧st，water := 0，i := 0
- 當i < height的長度時
- 如果棧為空或height[棧頂] >= height[i]，則將i壓入棧中，i加1
- 否則
- x := 棧頂元素，從棧中彈出棧頂元素
- 如果棧不為空，則
- temp := height[棧頂元素] 和 height[i] 的最小值
- dist := i – 棧頂元素 – 1
- water := water + dist * (temp – height[x])
- 返回water
讓我們來看下面的實現以更好地理解：
示例
class Solution(object): def trap(self, height): stack = [] water = 0 i=0 while i<len(height): if len(stack) == 0 or height[stack[-1]]>=height[i]: stack.append(i) i+=1 else: x = stack[-1] stack.pop() if len(stack) != 0: temp = min(height[stack[-1]],height[i]) dist = i - stack[-1]-1 water += dist*(temp - height[x]) return water ob = Solution() print(ob.trap([2,5,2,0,5,8,8]))
輸入
[2,5,2,0,5,8,8]
輸出
8
更新於：2020年10月20日
99 次檢視
廣告