劍指 Offer 30. 包含min函數(shù)的棧

定義棧的數(shù)據(jù)結(jié)構(gòu)，請在該類型中實現(xiàn)一個能夠得到棧的最小元素的 min 函數(shù)在該棧中，調(diào)用 min、push 及 pop 的時間復(fù)雜度都是 O(1)。

?

示例:

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.min();? ?--> 返回 -3.

minStack.pop();

minStack.top();? ? ? --> 返回 0.

minStack.min();? ?--> 返回 -2.

這題我主要是看大佬的題解，用輔助棧做的，大佬太厲害了。

class?MinStack:

????def?__init__(self):

????????"""

????????initialize?your?data?structure?here.

????????"""

????????self.A=[]

????????self.B=[]

????def?push(self,?x:?int)?->?None:

????????self.A.append(x)

????????if?not?self.B?or?self.B[-1]>=x:

????????????self.B.append(x)

????def?pop(self)?->?None:

????????if?self.A.pop()==self.B[-1]:

????????????self.B.pop()

????def?top(self)?->?int:

????????return?self.A[-1]

????def?min(self)?->?int:

????????return?self.B[-1]

#?Your?MinStack?object?will?be?instantiated?and?called?as?such:

#?obj?=?MinStack()

#?obj.push(x)

#?obj.pop()

#?param_3?=?obj.top()

#?param_4?=?obj.min()

另外在解題過程中發(fā)現(xiàn)，B！=None和not B是兩個概念，如果寫B(tài)!=None會導致編譯沒法通過。

百度了一下：

not B既包含了B=None，也包含了B=[]，B=‘’，B={}等多種為空的情況

因此在這里，想要判斷為空列表，B=None是判斷不了的，會顯示超出范圍，也就是說B仍然為空列表的情況沒有被考慮到。

當然如果情況是為樹就不太一樣，樹的left和right節(jié)點只能為None，因此not B和！=None都可以適用。