Leetcode題解 Python：四月挑戰DAY10 Min Stack

設計一個 stack，而且能在 O(1) 時間內回傳最小值。

stack是後進先出，如果眼前有書疊，要拿也是會從最上方拿起，最上方的書也是最後放的。

要實現stack，用list儲存資料就可以。

stack新增資料，用list.append()。 stack.pop => list.pop()。用list實現stack基本功能是沒有問題的。

這個 Min Stack 特別之處，在 O(1) 時間內回傳最小值，如果用 min()，而時間複雜度會是 O(n)。

因此在 Min Stack 的類別下，要有一個保存最小值的屬性，這樣才能第一時間回傳最小值。

用 int 保存可以嗎？

如果最後面加入的是最小值，然後被pop()掉，此時如果要調出此時的最小值，要怎麼處理？

如果連續加入兩個最小值，然後被pop()掉一個，又要怎麼處理最小值呢？

要是pop()掉的值是最小值，此時再用min()重新定位最小值，如果剛剛pop()掉的是僅剩的那一個元素呢？

如果考慮到stack的後進先出，這裡有個更妙的處理方式。就是使用一個minStack(list)。

加入的資料要是小於minStack[-1]的值，該值就順便加入到minStack。由於後進先出的特性，pop()掉的值一定會先遇到minStack[-1]，才會到[-2]、[-3]...

返還最小值，也只要回傳minStack[-1]就可以了。

class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack=[]
        self.mini_stack=[]

    def push(self, x: int) -> None:
        self.stack.append(x)
        if not self.mini_stack or x<=self.mini_stack[-1]:
            self.mini_stack.append(x)        

    def pop(self) -> None:
        if self.stack.pop() == self.mini_stack[-1]:
            self.mini_stack.pop()        
        
    def top(self) -> int:
        return self.stack[-1]        

    def getMin(self) -> int:
        return self.mini_stack[-1]