题解 | #包含min函数的栈#的Python解法

1. 解题思路

1.1 回顾栈的特性

只在一端插入和删除数据，并且数据存在先进后出，后进先出的特性。

1.2 图解示例

示例:
输入: ["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]
输出: -1,2,1,-1

根据示例，我们可以先初始化一个栈stack：
图片说明
接下来往里面依次添加“-1”，“2”进去：

此时的stack 中含有两个元素[-1, 2]。

第一个问题来了，如何调用min函数获取栈stack中的最小元素？？？
常规思路 就是对整个栈进行一个遍历，然后排序就能找到最小的元素，此时时间复杂度是O(n)。

但是本题要求👇

实现一个能够得到栈中所含最小元素的min函数，并且调用 min函数、push函数及 pop函数的时间复杂度都是 O(1)。

所以常规思路走不通❌，我们换一种思维。下面依然看图解：

首先初始化原始栈stack 和最小值栈stack_min(存储每次跟原栈中元素比较后的最小元素):
接下来插入（push） ‘1’这个元素，此时两个栈的变化如下图：
然后再插入（push） ‘2’这个元素，此时两个栈又变化如下图：
接着要获取栈顶元素，如下图：
而弹出栈顶元素，也直接调用pop函数 即可。
接着再次插入第三个元素 ‘1’，两个栈又发生如下变化👇：
最后再次利用top函数获取到栈顶元素就变成了 1，调用min函数则获取最小值依然是 -1。

2. 核心代码

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []  #初始化原栈
        self.stack_min = []  #初始化最小值栈
    def push(self, node):
        self.stack.append(node) #往原栈中添加 元素
        if not self.stack_min:    #一开始也往最小值栈中添加元素
            self.stack_min.append(node)
        elif node < self.stack_min[-1]:  #再次添加元素的时候要同最小值栈中元素比较，小于最小值栈中索引-1的对应值，就把node加入；
            self.stack_min.append(node)
        else:
            self.stack_min.append(self.stack_min[-1])  #否则把索引-1的对应值添加到stack_min中
    def pop(self):
        self.stack.pop()                    #弹出栈顶元素则分别获取即可
        self.stack_min.pop()
    def top(self):
        return self.stack[-1]                #栈顶元素从原栈中获取
    def min(self):
        return self.stack_min[-1]              #最小值就直接从最小值栈中获取

3.复杂度分析

时间复杂度：O(1) (由于每次入栈和出栈都只涉及栈顶元素的变动，所以是常量级O(1))
空间复杂度：O(n) (因为需要额外创建一个辅助栈stack_min)

------------------------------------------我是解法二的分割线-------------------------------------------

4. 解法二

4.1 思路

上面是辅助栈的解法，有没有不用辅助栈的解法？答案是肯定的！只需一个栈即可解决，核心思路用到了元组这个结构。即每次入栈和出栈都是一个元组，元组里面包含（当前数值x，栈内最小值）：

top获取的就是元组的第一个值；
min获取的就是元组的第二个值；
pop就是删除栈顶的这个元组；
push 则要分两种情况：
- 第一种：栈空的时候，直接压入元组（数值x，栈内最小值也是x）；
- 第二种：不为空，则比较两元组大小，取最小值压入（数值x，min(之前的栈内最小值，x)）。

4.2 核心代码

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack = []  #初始化原栈
    def push(self, node):
        if not self.stack: 
            #栈为空的情况，直接压入元组
            self.stack.append((node, node))
        #栈不为空的情况，取最小值压入
        else:
            self.stack.append((node, min(node, self.stack[-1][1])))
    def pop(self):
        self.stack.pop()                    #弹出栈顶元组
    def top(self):
        return self.stack[-1][0]                #栈顶元组的第一个值
    def min(self):
        return self.stack[-1][1]              #最小值就即元组的第二个值

4.3 复杂度分析

时间复杂度：O(1) (由于每次入栈和出栈都只涉及栈顶元素的变动，所以是常量级O(1))
空间复杂度：O(1) (由于就是在栈本身操作的，没用额外空间使用，所以也是常量的O(1))