最小栈

1、题目

图1

2、题解

最小插值法

当元素入栈时，只要没有加入更小值时，当前最小值是保持不变的。我们可以改变入栈元素内容，将当前入栈值与最小值插值入栈，这样可以根据最小值还原栈内值。

这样有一个新问题：最小值不是一直不变，当有更小值入栈时，最小值就会改变，原来记录的差值就不对了。

当更小值入栈，插值小于0，而之前的插值都是大于等于0。因此可以根据负数插值作为一个判断，表示再这个时候发生了最小值的改变。只有在元素出栈的时候才可能需要还原最小值，还原的最小值就是\(当前最小值-插值\)。

class MinStack:

    def __init__(self):
        self.diffs = []  # 存储入栈的元素
        self.min_val = 0 # 当前最小值

    def push(self, val: int) -> None:
        if not self.diffs:
            self.diffs.append(0)     # 当前栈内没有元素，差值为0入栈
            self.min_val = val      # 最小值为当前入栈元素
        else:
            self.diffs.append(val - self.min_val)    # 先记录差值
            self.min_val = min(val, self.min_val)   # 再更新最小值

    def pop(self) -> None:
        # 弹出栈顶差值
        # 如果差值为负，表示在这个位置最小值发生改变，需要还原原来的最小值
        # minVal = minVal - diff，否则最小值不变
        self.min_val -= min(self.diffs.pop(),0)

    def top(self) -> int:
        # 根据差值还原当前元素
        # 如果差值为负，说明当前位置发生了最小值改变，入栈值为最小值，记录的是和原来最小值的差值
        # 否则记录的差值是入栈值和当前最小值的差值，相加还原
        return self.min_val + max(self.diffs[-1], 0)

    def getMin(self) -> int:
        return self.min_val