問題描述：Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• pop() -- Removes the element on top of the stack.
• getMin() -- Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.

Chanllenge:

• 一個(gè)變量min無法完成記錄棧中所有狀態(tài)（所有方法）下的最小值
• so 使用另外一個(gè)stack記錄各個(gè)狀態(tài)的最小值
• 算法復(fù)雜的常數(shù)級(jí)別 O(1) time complexity. 所以需要空間換取時(shí)間

操作過程

代碼

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.data = []
        self.getmin = []
        

    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        self.data.append(x)       #不管怎樣data都要入棧，但是min需要不要入棧需要判斷
        if len(self.getmin) == 0:    #如果是第一個(gè)數(shù)字，目前肯定是最小數(shù)字所以入棧
            self.getmin.append(x)
        else:                     #如果不是第一個(gè)數(shù)字，那么比較min棧中最小的元素(棧里最上面的元素)與data進(jìn)棧的元素的大小決定min是否要進(jìn)棧
            if self.getmin[-1] >= x: #需要注意這個(gè)等于好=號(hào)
                self.getmin.append(x)
        

    def pop(self):
        """
        :rtype: void
        """
        if self.data:             #data不為空直接出棧，但是需要判斷min棧與data出棧元素是否相等決定min棧要不要進(jìn)行出棧操作
            if self.data[-1] == self.getmin[-1]:
                self.getmin.pop()
            self.data.pop()
        

    def top(self):
        """
        :rtype: int
        """
        if self.data:
            return self.data[-1]
        

    def getMin(self):
        """
        :rtype: int
        """
        if self.getmin:
            return self.getmin[-1]