維護一個單調堆疊，正序排列，進行遍歷，不滿足條件放入堆疊，滿足條件則對堆疊內元素所在位置處理，遍歷一次后所有元素解決
單調堆疊分為單調遞增堆疊或單調遞減堆疊，適用于需要比較大小關系且與元素位置有關的問題
單調堆疊方法：
1.構建堆疊儲藏滿足（遞增||遞減）關系的元素位置，一般按照題意反向取增減關系
2.遍歷，當第i個元素符合題意時，將之依次與堆疊中元素比較，pop元素，并求出元素對應所需值
3.依照題意取值
leetcode 42 接雨水說明單調堆疊
分析：
1.接雨水需要比較容器左右邊高
2.可以看成是多個容器拼接，容器位置關系與題目相關
因此可以使用單調堆疊=>拆分為多個長方形，長方形寬即位置差，高即與次高位置的高度差
class Solution:
def trap(self, height: List[int]) -> int:
if height==[]:
return 0
total = 0
#單調遞減堆疊
stack = [0]
#用0初始化一個lastpop,以確保當存在第一個高于堆疊內元素時高度不受lastpop影響
height.append(0)
#遍歷
for i in range(1,len(height)-1):
#初始化lastpop，使height[lastpop]=0
#當然，由于該題特殊性，每次第i個位置高度高于stack[-1]時，其與stack[-1]相鄰,不可能積水，積水寬度為0，因此可以直接讓lastpop初始化為stack[-1]
lastpop=len(height)-1
if stack:
while stack and height[i]>=height[stack[-1]]:
width = i - stack[-1]-1
total += (height[stack[-1]]-height[lastpop])*width
lastpop = stack.pop()
print(i,stack,total)
if stack != [] and height[i]<height[stack[-1]]:
total += (height[i]-height[lastpop])*(i-stack[-1]-1)
print(i,total)
#print(i,stack,total)
stack.append(i)
return total
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/258184.html
標籤：python
上一篇：MacOS系統下matplotlib中SimHei中文字體無法啟動解決辦法
下一篇：Python學習筆記（六）