[155][简单][栈][滑动窗口] 最小栈

题目描述

155. 最小栈 剑指 Offer 30. 包含min函数的栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

• push(x) —— 将元素 x 推入栈中。

• pop() —— 删除栈顶的元素。

• top() —— 获取栈顶元素。

• getMin() —— 检索栈中的最小元素。

示例:

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

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

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

• pop、top 和 getMin 操作总是在 非空栈 上调用

解题思路

辅助栈

Leetcode官方题解: 最小栈

栈的先进后出的性质, 决定, 如果一个元素 a 在入栈时, 栈里有其它的元素 b, c, d, 那么无论这个栈在之后经历了什么操作, 只要 a 在栈中, b, c, d 就一定在栈中. 因为在 a 被弹出之前, b, c, d 不会被弹出.

因此，在操作过程中的任意一个时刻，只要栈顶的元素是 a，那么我们就可以确定栈里面现在的元素一定是 a, b, c, d.

那么，我们可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 a，我们就可以直接返回存储的最小值 m.

过程:

设计一个数据结构, 使得每个元素 a 与其相应的最小值 m 时刻保持一一对应, 我们可以使用一个辅助栈, 与元素栈同步插入与删除, 用于存储与每个元素对应的最小值.

• 当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中

• 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出

• 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.num_stack = []
        self.min_stack = [float('inf')]  # 添加一个哨兵, 避免边界判断

    def push(self, x: int) -> None:
        self.num_stack.append(x)
        self.min_stack.append(min(x, self.min_stack[-1]))

    def pop(self) -> None:
        self.num_stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.num_stack[-1]

    def min(self) -> int:
        return self.min_stack[-1]

在存储当前步最小值的辅助栈中放入一个极大值, 作为哨兵, 避免每一步判断边际的操作.

不使用额外的空间

如果不能使用辅助栈, 就只能记录当前的最小值, 才能做到min方法的$O(1)$. 那么, 我们就要想办法, 在push和pop操作的时候, 对缓存的最小值进行更新, 使其被更新/还原成操作后栈顶对应的最小值.

结合以上的思路, 我们要在栈中存储的值, 就不能再是数值本身, 而是要存储当前数值与操作前最小值的差值.

• 如果这个差值小于0, 说明当前值是最小值. 在pop的过程中遇到, 说明将这个数pop出去后, 最小值就要更新, 要变大, 而新的最小值就是当前最小值减去这个差值

• 如果这个差值大于0, 说明最小的值还在栈中, 无需更新最小值

class MinStack:

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

    def push(self, x: int) -> None:
        if len(self.stack) == 0:
            self.stack.append(0)
            self.current_min = x
        else:
            diff = x - self.current_min
            self.stack.append(diff)
            if diff < 0:
                self.current_min = x

    def pop(self) -> None:
        diff = self.stack.pop()
        if diff < 0:
            self.current_min -= diff

    def top(self) -> int:
        return self.stack[-1] + self.current_min if self.stack[-1] >= 0 else self.current_min

    def min(self) -> int:
        return self.current_min