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

核心思路

用两个栈来实现：

• 一个用来正常存储一个栈(st1)，另一个栈用来存当前最小值(st2)。
• 进来一个数，st1直接放进去就好，st2的话要做以下判断
  • 如果st2为空，直接放进去
  • 如果st2不为空，则判断 新进来的值 和 st2的top值 的大小
    • 新进来的值小，就直接放进去
    • 原栈顶小，则将原栈顶重复放进去一次（这样可以保持st2的栈顶一直是最小值）

c++实现

class Solution {
public:
    stack<int> st1, st2;
    void push(int value) {
        st1.push(value);
        if(st2.empty()){
            st2.push(value);
        }else{
            if(value < st2.top()){
                st2.push(value);
            }else{
                st2.push(st2.top());
            }
        }
    }
    
    void pop() {
        st1.pop();
        st2.pop();
    }
    
    int top() {
        return st1.top();
    }
    
    int min() {
        return st2.top();
    }
};