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

## 题目描述

[155. 最小栈](https://leetcode-cn.com/problems/min-stack/) [剑指 Offer 30. 包含min函数的栈](https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/)

设计一个支持 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官方题解: 最小栈](https://leetcode-cn.com/problems/min-stack/solution/zui-xiao-zhan-by-leetcode-solution/)

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

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

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

![](/files/-MFRBZloInwOTBCzBwZm)

过程:

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

* 当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中
* 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出
* 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中

```python
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, 说明最小的值还在栈中, 无需更新最小值

```python
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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blessbingo.gitbook.io/garnet/suan-fa/zhan/155-zui-xiao-zhan.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.