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

一.题意整理

定义栈的数据结构，栈是一个先进后出的数据结构，下面将实现如下的函数功能：

push(value)：将value压入栈中
pop()：弹出栈顶元素
top()：获取栈顶元素
min()：获取栈中最小元素
例如：栈：2 5 6 23 17
分别实现：
push(9)后栈序列：2 5 6 23 17 9 
pop()后栈序列：2 5 6 23 
top()返回值是栈顶元素：17
min()返回栈中的最小元素：2

二.思路整理

首先会给大家介绍c++中的STL，STL是标准模板库（Standard Template Library)是c++内置实现的函数模板，其中包括了栈的实现。

stack<type>函数名字 实现对栈的定义
empty() 堆栈为空则返回真
pop() 移除栈顶元素
push() 在栈顶增加元素
size() 返回栈中元素数目
top() 返回栈顶元素

然后我们回到本题目，要对于入栈、出栈、栈顶在STL中都已经实现好了，但是对于返回最小值的操作却没有实现，可能有人说遍历一遍不就可以了，但是在STL中stack是不支持遍历，那么对于最小值我们该如何实现呢？我们可以利用一个辅助栈来实现对最小值的维护。对于每一次入栈的元素我们对其进行判断，要是入栈元素小于当前辅助栈的栈顶，那么目前最小值就是当前入栈元素;若入栈元素大于当前辅助栈的栈顶，那么很显然当前元素的加入不影响最小值，那么就将辅助栈的栈顶入栈，来维持最小值。那么在每次出栈的时候，由于辅助站都是维护栈顶元素的最小值，所以在出栈的时候辅助栈和主栈都要同时出栈。

三.代码实现

class Solution {
public:
    stack<int>st,mi;
    //利用STL中的定义两个栈
    //st是辅助栈
    void push(int value) {
        st.push(value);
        if(!mi.size()){
            mi.push(value);
        } else {
            //辅助站的为维护
            if(value<=mi.top()){
                mi.push(value);
            } else {
                mi.push(mi.top());
            }
        }
    }
    void pop() {
        //由于辅助站的维护 两个栈都必须同时出栈
        st.pop();
        mi.pop();
    }
    int top() {
        return st.top();
    }
    int min() {
        //返回辅助栈的最小元素
        return mi.top();
    }
};