最小栈

## 1 题目

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

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
**示例:**

```txt
输入：
["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 操作总是在 非空栈 上调用。

## 2 解题思路

### 2.1 一个栈同时保存当前值和栈内最小值

#### 2.1.1 问题分析

1. 可以**用一个栈**，**这个栈同时保存的是每个数字 $x$ 进栈的时候的值与插入该值后的栈内最小值**，即**每次新元素 $x$ 入栈的时候保存一个元组**（Java 中没有元组的概念，但是可以使用字符串进行拼接，思路是一样的，为了叙述方便，下面统一用元组来叙述）。
2. **这个元祖是一个整体**，**同时进栈和出栈**，即**栈顶同时有值和栈内最小值**，此时各个函数的具体含义如下
   1. `top()`**函数是获取栈顶当前值**，即**栈顶元组的第一个值**。
   2. `getMin()` **函数是获取栈内最小值**，即**栈顶元组的第二个值**。
   3. `pop()`**函数是删除栈顶元组**。
3. **每次新元素入栈时**，**要求新的栈内最小值**，**需要比较当前新插入元素 $x$ 和当前栈内最小值**（即栈顶元组的第二个值）的大小：
   1. **当栈为空的时候**，**保存元祖** $(x, x)$。
   2. **当栈不为空的时候**，**保存元祖** $(x, min(此前栈内最小值), x)$。
4. **出栈的时候**，**直接删除栈顶元组即可**。

#### 2.1.2 参考代码

```java
/**
 * 方法一：一个栈同时保存当前值和栈内最小值
 */
class MinStack {

Stack<String> stack;
    int index, minVal;

public MinStack() {
        stack = new Stack<>();
        index = 0;
        minVal = Integer.MAX_VALUE;
    }

public void push(int val) {
        if (stack.size() == 0) {
            //  如果当前栈为空，则最小值为当前要插入的元素
            minVal = val;
        } else {
            //  如果当前栈不为空，则最小值为栈顶元素中存储的最小值与当前要插入的元素之间的最小值
            minVal = Math.min(val, Integer.parseInt(stack.peek().split("_")[2]));
        }
        //  将拼接好的数据插入栈中，格式为 索引_要插入的元素_当前最小值
        stack.push(String.format("%s_%s_%s", index++, val, minVal));
    }

public void pop() {
        stack.pop();
    }

public int top() {
        return Integer.parseInt(stack.peek().split("_")[1]);
    }

public int getMin() {
        return Integer.parseInt(stack.peek().split("_")[2]);
    }
}
```

### 2.2 辅助栈

#### 2.2.1 问题分析

1. **辅助栈的基本原理是使用两个栈**，分别为 $stack$、$stack2$，其中 $stack$ **用于保存当前的元素**，$stack2$ **用于保存当前最小的元素**。
2. **当插入一个元素 $val$ 时**：
   1. **将 $val$ 插入 $stack$**。
   2. **如果 $stack2$ 不为空**，并且**当前插入的元素小于等于 $stack2$ 的栈顶元素**，则**将 $val$ 插入 $stack2$**。
3. **当删除一个元素时**，**将 $stack$ 进行 $pop$**，**如果 $stack$ 删除的元素和 $stack2$ 的栈顶元素一样**，**则将 $stack2$ 也进行 $pop$**。
4. **当需要获取栈顶元素时**，**直接返回 $stack.peek()$ 即可**。
5. **当需要获取最小元素时**，**直接返回 $stack2.peek()$**。

#### 2.2.2 参考代码

```java
/**
 * 方法二：辅助栈
 */
class MinStack {
    Stack<Integer> stack;
    Stack<Integer> stack2;
    public MinStack() {
        stack = new Stack<>();
        stack2 = new Stack<>();
    }
    public void push(int val) {
        stack.push(val);
        if (stack2.size() == 0 || val <= stack2.peek()) {
            //  如果 stack2 不为空，并且当前插入的元素小于等于 stack2 的栈顶元素，则将 val 插入 stack2
            stack2.push(val);
        }
    }
    public void pop() {
        int val = stack.pop();
        if (stack2.peek() == val) {
            //  如果 stack 删除的元素和 stack2 的栈顶元素一样，则将 stack2 也进行 pop
            stack2.pop();
        }
    }
    public int top() {
        return stack.peek();
    }
    public int getMin() {
        return stack2.peek();
    }
}
```

## 3 扩展题目

### 3.1 [队列的最大值](https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof)

#### 3.1.1 问题分析

1. 如下图所示，我们考虑**构建一个递减列表来保存队列所有递减的元素**，**递减列表随着入队和出队操作实时更新**，**这样队列最大元素就始终对应递减列表的首元素**，**实现了以 $O(1)$ 时间复杂度获取最大值**。
2. **为了实现此递减列表**，**需要使用双向队列**，**假设队列已经有若干元素**：

1. **当执行入队时**，**若入队一个比队列某些元素更大的数字 $x$**，**则为了保持此列表递减**，**需要将双向队列尾部所有小于 $x$ 的元素弹出**。
   2. **当执行出队时**，**若出队的元素是最大的元素**，**则双向队列需要同时将首元素出队**，**以保持队列和双向队列元素的一致性**。

> **使用双向队列是因为维护递减列表需要元素队首弹出**、**队尾插入**、**队尾弹出操作皆为 $O(1)$ 时间复杂度**。
      >
3. 具体的函数设计如下：

1. **初始化队列 $queue$**，**双向队列 $helper$**。

![](/media/202206/2022-06-13_105043_201086.png)
   2. **最大值 `max_value()`**：

1. **当双向队列 $helper$ 为空**，**则返回-1**。
      2. **否则**，**返回 $helper$ 首元素**。

![](/media/202206/2022-06-13_105159_294886.png)
   3. **入队 `push_back()`**：

1. **将元素 $value$ 入队 $queue$**。
      2. **将双向队列中队尾所有小于 $value$ 的元素弹出**（以保持 $helper$），**并将元素 $value$ 入队 $helper$**。

![](/media/202206/2022-06-13_105243_947377.png)

![](/media/202206/2022-06-13_105254_040460.png)

![](/media/202206/2022-06-13_105303_856847.png)

![](/media/202206/2022-06-13_105313_190196.png)

![](/media/202206/2022-06-13_105321_893818.png)

![](/media/202206/2022-06-13_105333_848594.png)
   4. **出队 `pop_front()`**：

1. **若队列 $queue$ 为空**，**则直接返回-1**。
      2. **否则**，**将 $queue$ 首元素出队**。
      3. **若 $helper$ 首元素和 $queue$ 首元素相等**，**则将 $helper$ 首元素出队**（以保持两队列元素一致）。

![](/media/202206/2022-06-13_105408_271440.png)

![](/media/202206/2022-06-13_105428_782343.png)

![](/media/202206/2022-06-13_105438_555110.png)

![](/media/202206/2022-06-13_105448_085033.png)

![](/media/202206/2022-06-13_105457_374648.png)

![](/media/202206/2022-06-13_105534_043335.png)

![](/media/202206/2022-06-13_105543_788476.png)

![](/media/202206/2022-06-13_105553_304979.png)

![](/media/202206/2022-06-13_105602_624825.png)

![](/media/202206/2022-06-13_105612_539738.png)
4. 具体实例如下：

![](/media/202206/2022-06-13_105652_720341.gif)

#### 3.1.2 参考代码

```java
/**
 * 剑指 Offer 59 - II. 队列的最大值
 */
class MaxQueue {

Queue<Integer> queue;
    Deque<Integer> helper;

public MaxQueue() {
        queue = new LinkedList<>();
        helper = new LinkedList<>();
    }

public int max_value() {
        return helper.size() > 0 ? helper.peekFirst() : -1;
    }

public void push_back(int value) {
        queue.add(value);
        while (helper.size() != 0 && helper.peekLast() < value) {
            helper.pollLast();
        }
        helper.add(value);
    }

public int pop_front() {
        if (queue.size() == 0) {return -1;}
        int tmp = queue.poll();
        if (tmp == helper.peekFirst()) {
            helper.pollFirst();
        }
        return tmp;
    }
}
```

## 参考文献

1. [155. 最小栈](https://leetcode-cn.com/problems/min-stack)。
2. [一个栈同时保存当前值和栈内最小值](https://leetcode-cn.com/problems/min-stack/solution/zui-yi-dong-yi-ge-zhan-tong-shi-bao-cun-dang-qian-)。
3. [剑指 Offer 59 - II. 队列的最大值](https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof)。
4. [剑指 Offer 59 - II. 队列的最大值（单调双向队列，清晰图解）](https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/solution/jian-zhi-offer-59-ii-dui-lie-de-zui-da-z-0pap)。