題目描述
定義棧的數(shù)據(jù)結(jié)構(gòu)舷暮，請在該類型中實現(xiàn)一個能夠得到棧中所含最小元素的min函數(shù)（時間復雜度應為O（1））杏节。
知識點
棧
Qiang的思路
對于這個問題中描述的這個棧和普通的棧的區(qū)別在于具有求最小元素的功能辕宏，那么，這個棧應該不止能將數(shù)據(jù)壓入阵苇、彈出轮纫，還能夠獲得棧中的最小元素。顯然洪添，我們可以維護一個最小元素垦页，當數(shù)據(jù)入棧時，需要將當前最小元素進行更新干奢，當數(shù)據(jù)出棧時也需要將最小的數(shù)據(jù)進行更新痊焊，但是這樣每次出棧和入棧的時候都會重新計算一下當前的最小元素，時間復雜度肯定是高的忿峻。
所以薄啥，可以考慮空間換時間，維護一個和棧綁定的最小元素棧逛尚，這個最小元素棧中存放著與題目要的棧對應的最小元素值垄惧，這樣，每次要求最小的元素時绰寞，我們只需要將當前狀態(tài)對應的最小元素獲得即可到逊。同時，因為兩者是綁定的克握，所以當更新題目要求的棧時需要同步的對最小元素棧進行更新蕾管。但壓入元素時，將上一時刻的最小元素和當前元素進行對比菩暗，更小的元素為當前時刻的最小元素掰曾，當彈出元素時，只需要將對應狀態(tài)的最小元素彈出即可停团。
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.m=[]
self.s=[]
def push(self, node):
# write code here
self.m.append(self.m[-1] if self.m!=[] and self.m[-1]<node else node)
self.s.append(node)
def pop(self):
# write code here
if self.s==[]:
return None
self.m.pop(-1)
return self.s.pop(-1)
def top(self):
# write code here
return self.s[-1]
def min(self):
# write code here
return self.m[-1]
作者原創(chuàng)旷坦，如需轉(zhuǎn)載及其他問題請郵箱聯(lián)系：lwqiang_chn@163.com。
個人網(wǎng)站：https://www.myqiang.top佑稠。
