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

1、要用两个栈，stack用于存储元素，mins用于存储最小值，每个位置的元素都有一个对应的最小值，也就是stack和mins的长度同步增加和减少；当需要得到目前栈中的最小值的时候，直接返回mins的栈顶元素即可
2、在mins栈中先添加一个最大值，因为以后每次添加都会和栈顶元素比较，如果栈为空的话代码要多写几行，先放一个最大值会方便一点

Python版本

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.mins = [float("inf")]
        
    def push(self, node):
        # write code here
        self.stack.append(node)
        self.mins.append(min(self.mins[-1], node))
    def pop(self):
        # write code here
        self.stack.pop()
        self.mins.pop()
    def top(self):
        # write code here
        return self.stack[-1]
    def min(self):
        # write code here
        return self.mins[-1]

复杂度分析：

时间复杂度O(1)：栈的入、出时间均为O(1)

空间复杂度O(N)：辅助栈空间，最差情况辅助站存储元素n个

算法思想二：基于链表

解题思路：

两个List一个存放存取的东西，一个存放截至到当前下标的最小值：
1.入栈一个数字就入栈一个当前位置最小值；
2.出栈一个数字就出栈尾位置最小值；

代码展示：

JAVA版本

import java.util.List;
import java.util.ArrayList;

public class Solution {
    // 存储最小元素数组
    Listmin = new ArrayList();
    // 存储入栈数组
    Listnum = new ArrayList();
    
    public void push(int node) {
        num.add(node);
        // 判断最小值存入min数组
        if(min.size() == 0 || node < min.get(min.size() - 1)) min.add(node); 
        else min.add(min.get(min.size() - 1)); } 
    public void pop() { 
        num.remove(num.size() - 1); 
        min.remove(min.size() - 1); 
    } 
    public int top() { // 获取最后一个元素 
        return num.get(num.size() - 1); 
    } 
    public int min() { 
        return min.get(min.size() - 1); 
    } 
}