題目
定義棧的數(shù)據(jù)結(jié)構(gòu)氯质，請(qǐng)?jiān)谠擃愋椭袑?shí)現(xiàn)一個(gè)能夠得到棧最小元素的min函數(shù)髓涯。
思路
主要有兩種思路
- （時(shí)間換空間）只維護(hù)一個(gè)棧杂数，需要取最小值的時(shí)候?qū)Ｖ械脑剡M(jìn)行遍歷，找出最小值锉试。當(dāng)棧非常大的時(shí)候猫十，這種思路的代價(jià)就很大。
- （空間換時(shí)間）多維護(hù)一個(gè)最小值棧
min_stack呆盖。每次push的時(shí)候拖云，檢查最小值棧是否為空，若為空直接插入应又，不為空則判斷插入值是否小于棧頂元素宙项，若小于則插入。pop時(shí)我們?nèi)绻钚≈禇ｍ數(shù)脑睾蚿op的元素相等丁频，則將最小值棧頂元素也pop出去杉允。
有人可能會(huì)問(wèn)邑贴，為什么需要維護(hù)最小值棧呢席里，直接維護(hù)最小值不就好了嗎？問(wèn)題在于我們是有可能pop的拢驾，萬(wàn)一stack中被pop出去的值剛好是你記錄的最小值奖磁，此時(shí)你就不知道接下來(lái)的最小值該取什么了。
代碼
思路二
class Solution:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, node):
# write code here
self.stack.append(node)
if not self.min_stack or self.min_stack[-1] > node:
self.min_stack.append(node)
def pop(self):
# write code here
pop = self.stack.pop()
if self.min_stack[-1] == pop:
self.min_stack.pop()
return pop
def top(self):
# write code here
return self.stack[-1]
def min(self):
# write code here
return self.min_stack[-1]
