155.MinStack (LeetCode)

问题描述：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:

• 一个变量min无法完成记录栈中所有状态（所有方法）下的最小值
• so 使用另外一个stack记录各个状态的最小值
• 算法复杂的常数级别 O(1) time complexity. 所以需要空间换取时间

操作过程

代码

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:    #如果是第一个数字，目前肯定是最小数字所以入栈
            self.getmin.append(x)
        else:                     #如果不是第一个数字，那么比较min栈中最小的元素(栈里最上面的元素)与data进栈的元素的大小决定min是否要进栈
            if self.getmin[-1] >= x: #需要注意这个等于好=号
                self.getmin.append(x)
        

    def pop(self):
        """
        :rtype: void
        """
        if self.data:             #data不为空直接出栈，但是需要判断min栈与data出栈元素是否相等决定min栈要不要进行出栈操作
            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]