設(shè)計(jì)一個(gè)有g(shù)etMin功能的棧
要求：pop斧抱、push娇豫、getMin操作的時(shí)間復(fù)雜度都是O(1)耀找，設(shè)計(jì)時(shí)可以使用現(xiàn)成的棧結(jié)構(gòu)
思路：使用兩個(gè)棧此洲，一個(gè)棧stackData用來保存當(dāng)前棧中的元素厂汗，和普通棧沒區(qū)別，另一個(gè)棧stackMin用于保存每一步的最小值呜师。
（1）壓入數(shù)據(jù)規(guī)則
如果當(dāng)前數(shù)據(jù)為newNum娶桦，先將其壓入stackData。然后判斷stackMin是否為空：
- 如果為空汁汗，則newNum也壓入stackMin
- 否則衷畦，比較nuwNum和stackMin棧頂元素哪一個(gè)更小
- 如果newNum更小或者兩者相等，則newNum也壓入stackMin
- 否則stackMin不壓入任何內(nèi)容
（2）彈出數(shù)據(jù)規(guī)則
先在stackData中彈出棧頂元素知牌，記為value祈争。value等于stackMin的棧頂元素時(shí)，彈出該棧頂元素角寸，否則不彈出棧頂元素菩混，返回value。
class MinStack(object):
def __init__(self):
self.stackData = []
self.stackMin = []
def push(self, x):
self.stackData.append(x)
if len(self.stackMin) == 0 or x<=self.getMin():
self.stackMin.append(x)
def pop(self):
if len(self.stackData) == 0:
return
value = self.stackData.pop()
if value == self.stackMin[-1]:
self.stackMin.pop()
return value
def top(self):
if len(self.stackData) == 0:
return
return self.stackData[-1]
def getMin(self):
if len(self.stackMin) == 0:
return
return self.stackMin[-1]
