leetcode155. 最小栈

一、题目描述：

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

二、输入输出实例：

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

三、思路讲解：

• 创建两个stack对象，stack1用来存储入栈元素，stack2用来存储栈当前最小元素。
• push函数思路：

        ①无论什么情况stack1都需要压栈。

        ②当stack2为空，或者stack2栈顶的元素和当前需要压栈的元素相等时，stack2执行压         栈操作。

• pop函数思路：

        ①无论什么情况stack1都需要出栈。

        ②当stack2栈顶元素和stack1栈顶元素相等时，stack2执行出栈。

        ③当stack2不和stack1栈顶元素相等，说明要出栈的元素不是stack1栈中当前最小元素 

        那么这个元素可以直接弹出。

• 构造函数可以删掉，删掉后编译器会生成默认构造函数；不删掉也可以不用理会，因为这个类只有内置类型，所有内置类型都会自己走初始化列表。
• top函数返回stack1的栈顶元素即可。
• getMin返回stack2栈顶元素即可，stack2栈顶元素是当前栈中最小的元素。

四、C++代码：

class MinStack {
    stack<int> s1;
    stack<int> s2;
public:
    MinStack()
    {
        //不用写，内置类型会自己走初始化列表
    }
    
    void push(int val)
    {
        s1.push(val);//主栈压栈
        if(s2.empty()||val<=s2.top())//辅栈如果为空，或者val小于辅栈栈顶元素
                                     //辅栈压栈
        {
            s2.push(val);
        }
    }
    
    void pop()
    {
        if(s1.top()==s2.top())//如果主栈和辅栈的栈顶元素大小相等
                              //辅栈出栈
        {
            s2.pop();
        }
        s1.pop();//主栈无论如何都出栈
    }
    
    int top()//返回主栈的栈顶位置元素
    {
        return s1.top();
    }
    
    int getMin()//返回辅栈的栈顶元素，也就是主栈最小元素
    {
        return s2.top();
    }
};