[Python知识库]剑指offer—包含min函数的栈

题目： 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数，并且调用 min函数、push函数 及 pop函数的
时间复杂度都是 O(1)
push(value):将value压入栈中
pop():弹出栈顶元素 top():获取栈顶元素
min():获取栈中最小元素

这个题目的话，我用我这空荡荡的的脑子想出了简单的代码，省时省力，哈哈哈
下面这个是我自己写的，一个函数一行代码，但是这个写法运行的时间较其他方法更长

class Solution:  # 自己写的，简单易懂
    def __init__(self):
        self.stack = []

    def push(self, node):
        self.stack.append(node)

    def pop(self):
        self.stack.pop()

    def top(self):
        return self.stack[-1]

    def min(self):
        return min(self.stack)

??下面这个方法是大佬用Java写的，我改成python的了，不知道对不对，反正提交是正确的，那就假装它是对的
??这个方法的思路很巧妙，利用最小值和存储的数字的差值来记录最小值，我自己加了一些注释

class Solution:
    def __init__(self):
        self.stack = []
        self.top_ = None
        self.min_ = None

    def push(self, node):  # 入栈操作
        if not self.stack:  # 第一次入栈比较特殊，入栈即为最小
            self.min_ = node
        self.stack.append(node - self.min_)  # 将即将入栈的元素和最小值min相减，将差值入栈
        if node < self.min_:  # 即将入栈的元素如果比当前的min值小，那么替换min值
            self.min_ = node
        self.top_ = node  # 更新栈顶的元素

    def pop(self):  # 出栈操作
        if self.stack:  # 当栈中有元素的时候
            if self.stack[-1] < 0:  # 如果栈顶存储的差值是负数，那么就说明即将要出栈的值是最小值min
                self.min_ -= self.stack[-1]  # 更新当前的最小值
            self.stack.pop()  # 弹出
        if self.stack:  # 当弹出栈顶元素以后，栈中还有元素时
            if self.stack[-1] > 0:  # 如果栈顶元素是正数，那么说明现在的栈顶元素不是最小值
                self.top_ = self.stack[
                    -1] + self.min_  # 那么正常使用差值加最小值求出栈顶本来的元素即可
            else:  # 如果栈顶不是正数，那么说明此时栈顶的元素为当前的最小值
                self.top_ = self.min_

    def top(self):
        return self.top_

    def min(self):
        print(self.min_)
        return self.min_

相对上一种方法来说，下面这个方法就简单易懂了，但是本来的代码写的很烂，稍稍改了一下，在push函数中，if判断语句后本来的顺序是if min>node or not min，这么一来当第一次添加数据的时候就会出错，因为min本来不存在，所以在判断第一个条件的时候程序就因为异常而退出了，并不会进入not min的判断中。但如果更换两者的顺序if not min or min > node，那么就会先判断not min，min如果不存在，那么not min就为真，进入循环。
??这里小扯一下，if的判断时，先以if A or B为例，如果条件A成立，那么if不会去判断条件B是否成立，if成立；反之则去判断条件B，如果条件B成立，if才成立。
??if A and B同理，当条件A为假的时候，计算机不会再去判断条件B了，if直接就不成立；反之，再去判断条件B，如果条件B成立，则if成立。

class Solution():  # 借助临时的数组来存储最小的值
    def __init__(self):
        self.stack = []# 存储元素的普通栈
        self.auxiliary = []# 存储最小值的数组，栈顶的元素是stack里的最小值

    def push(self, node):
        min = self.min()# 直接将当前对象的最小值利用自带的函数求出来
        if not min or min > node:# 当min不存在（输入第一个数的时候）或输入的值比当前对象的最小值还小的时候
            self.stack.append(node)# 将值入栈
            self.auxiliary.append(node)# 将值放入最小值的栈
        else:# 如果输入的值不是最小的值，那么只添加进普通的栈
            self.stack.append(node)

    def pop(self):
        if self.stack:# 当栈中有元素的时候
            if self.stack[-1] == self.auxiliary[-1]:# 如果即将要弹出栈的值是最小值，那么下面两个栈同时弹出
                self.stack.pop()
                self.auxiliary.pop()
            else:# 弹出的不是最小值时，只弹出普通栈的元素
                self.stack.pop()

    def top(self):
        if self.stack:
            return self.stack[-1]# 返回普通栈的栈顶元素

    def min(self):
        if self.auxiliary:
            return self.auxiliary[-1]# 返回栈顶元素