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

思路

• 用两个栈来实现
• 一个是普通栈，处理入栈出栈的问题
• 另一个是最小栈，装的是普通栈中目前的最小值，随着普通栈的入栈退栈进行同时变化

方法一：利用已有栈写法（c++）

• 关键是一定要保证最小值栈在实时跟随普通栈的变化，这样维护的最小值栈的栈顶才能随时返回来题干中要求的最小值

class Solution {
public:
    stack<int> s1;  //用于栈的push 与 pop
    stack<int> s2;  //用于存储最小min
    void push(int value) {
        s1.push(value);  
        if(s2.empty() || s2.top() > value)  //空或者新元素较小，则入栈
            s2.push(value);
        else
            s2.push(s2.top());  //重复加入栈顶
    }
    void pop() {
        s1.pop();
        s2.pop();
    }
    int top() {
        return s1.top();
    }
    int min() {
        return s2.top();
    }
};

复杂度分析

• 时间复杂度：O(1)，每个操作只需要常数时间访问
• 空间复杂度：O(N)，需要申请的栈空间的代价

方法二：自己写一个栈类并使用（python3）

自己写一个栈就借助list数据结构，处理好先进后出的规则即可

# -*- coding:utf-8 -*-
class Stack():   #定义类
    def __init__(self):  #产生一个空的容器
        self.__list = []
    def push(self, item):  #入栈
        self.__list.append(item)
    def pop(self):  #出栈
        return self.__list.pop()
    def speek(self):  #返回栈顶元素
        return self.__list[-1]
    def is_empty(self):  #判断是否已为空
        return not self.__list
    def size(self):  #返回栈中元素个数
        return len(self.__list)

class Solution:
    def __init__(self):
        self.s1 = Stack() #普通栈
        self.s2 = Stack() #最小栈

    def push(self, node):
        # write code here
        self.s1.push(node)
        if self.s2.is_empty() or self.s2.speek() > node:    #最小栈要满足当前元素大于栈顶元素才入栈
            self.s2.push(node)
        else:
            self.s2.push(self.s2.speek())                   #如果不满足刚才的情况则将暂时的最小值再次入栈，保证两个栈内元素个数相等
    def pop(self):
        # write code here
        self.s1.pop()
        self.s2.pop()
    def top(self):
        # write code here
        return self.s1.speek()
    def min(self):
        # write code here
        return self.s2.speek()

复杂度分析

• 时间复杂度：O(1)，每个操作只需要常数时间访问
• 空间复杂度：O(N)，需要申请的栈空间的代价