題目
棧是一種常見的數(shù)據(jù)結構，其特點是 先進后出镜会，也就是說最先放進去的元素终抽，需要到最后才能取出來。
請使用 列表list 實現(xiàn)一個能在 常數(shù)時間 內(nèi)檢索到最小元素的棧匾旭，需實現(xiàn)以下操作：
- push(x) -- 將元素 x 壓入棧頂
- pop() -- 移除棧頂元素
- top() -- 獲取棧頂元素
- min() -- 檢索并返回棧中的最小元素
- empty() -- 判斷棧是否為空
- size() -- 獲取棧的長度
說明：假設每次調用 pop / top / min 操作都能保證棧不為空亩码。
實現(xiàn)思路1
- 使用一個棧 s 用于保存每個元素，另外再使用一個棧 min_s 用于保存當前的最小值
- 每次入棧時飒泻，把元素壓入棧 s 的棧頂吏廉，同時把棧 s 中的最小值，壓入棧 min_s 的棧頂
- 每次出棧時史辙，兩個棧都需要執(zhí)行 pop() 操作
- 如果要獲取棧頂元素，則直接取棧 s 的棧頂元素晦毙；如果要獲取棧中的最小值耙蔑，則直接取棧 min_s 的棧頂元素
代碼實現(xiàn)1
class MinStack:
def __init__(self):
self.s = []
self.min_s = []
def push(self, x):
self.s.append(x)
if self.min_s == [] or self.min_s[-1] > x:
self.min_s.append(x)
else:
self.min_s.append(self.min_s[-1])
def pop(self):
self.s.pop()
self.min_s.pop()
def top(self):
return self.s[-1]
def min(self):
return self.min_s[-1]
def empty(self):
return self.s == []
def size(self):
return len(self.s)
實現(xiàn)思路2
- 只使用一個棧，同時保存當前值和棧內(nèi)的最小值
- 每次入棧時须揣，入棧元素為元組形式：
（最小值钱豁，當前值）纷纫，每次出棧時戳玫，把棧頂?shù)脑M執(zhí)行出棧即可 - 因為棧頂?shù)脑M中同時保存了棧內(nèi)的最小值和棧頂?shù)漠斍爸盗菖欤詶ｍ斣M中估蹄，第一個值即為棧內(nèi)最小值，第二個值即為棧頂當前值
代碼實現(xiàn)2
class MinStack:
def __init__(self):
self.s = []
def push(self, x):
if self.s == [] or self.s[-1][0] > x:
self.s.append((x, x))
else:
self.s.append((self.s[-1][0], x))
def pop(self):
self.s.pop()
def top(self):
return self.s[-1][1]
def min(self):
return self.s[-1][0]
def empty(self):
return self.s == []
def size(self):
return len(self.s)
更多Python編程題最铁，等你來挑戰(zhàn)：Python編程題匯總（持續(xù)更新中……）
