最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶部的元素。 int getMin() 获取堆栈中的最小元素。

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

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

    def push(self, x ) :
        if not self.stack:
            self.stack.append(0)   #diff=0
            self.min_value = x
        else:
            diff = x - self.min_value
            self.stack.append(diff)
            if diff < 0:
                self.min_value = x  # x= min_value  此种情况下pop时 min_value=x-diff 即 min_value=min_value-diff

    def pop(self) :                      ##这里要求返回None，所以不用出栈的值是多少
        if self.stack:
            diff = self.stack.pop()
            if diff < 0:
                min = self.min_value
                self.min_value = min - diff


    def top(self):
        return self.min_value if self.stack[-1] < 0 else self.stack[-1] + self.min_value

    def getMin(self):
        return self.min_value if self.stack else -1


stack1 = MinStack()
stack1.push(-2)
stack1.push(0)
stack1.push(-3)
print(stack1.getMin())
print(stack1.pop())
print(stack1.top())
print(stack1.stack)


# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

思路：通过在栈中记录与最小值的差值。入栈时，计算差值并把差值入栈；出栈时以最小值为基准加上差值，不用辅助栈节省了空间
缺点：部分代码可读性差，但是运行快且省了空间~