資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究Python 中的最小棧
這裡我們將瞭解如何編寫棧，它可以在常量時間內執行 push、pop、top 和檢索最小元素。因此，函式為 push(x)、pop()、top() 和 getMin()
為此，我們將遵循以下步驟 −
- 初始化棧，其中最小元素為無窮大
- 對於 push 操作 push(x)
- 如果 x < 最小值，則更新最小值 := x，
- 將 x 推入棧中
- 對於 pop 操作 pop()
- t := 頂部元素
- 從棧中刪除 t
- 如果 t 為最小值，則最小值 := 棧中的頂部元素
- 對於 top 操作 top()
- 直接返回頂部元素即可
- 對於 getMin 操作 getMin()
- 返回最小元素
示例
讓我們看看以下實現，以更好地理解 −
class MinStack(object):
min=float('inf')
def __init__(self):
self.min=float('inf')
self.stack = []
def push(self, x):
if x<=self.min:
self.stack.append(self.min)
self.min = x
self.stack.append(x)
def pop(self):
t = self.stack[-1]
self.stack.pop()
if self.min == t:
self.min = self.stack[-1]
self.stack.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.min
m = MinStack()
m.push(-2)
m.push(0)
m.push(-3)
print(m.getMin())
m.pop()
print(m.top())
print(m.getMin())輸入
m = MinStack() m.push(-2) m.push(0) m.push(-3) print(m.getMin()) m.pop() print(m.top()) print(m.getMin())
輸出
-3 0 -2
更新於：2020 年 4 月 28 日
2K+ 瀏覽
廣告