LeetCode: Min Stack最小值栈

睡不着,起来写道题

言归正传:

• 其实这道题很简单,不过我之前腾讯的实习生面试的时候还遇到过这道题,所以还是可以做做,其实最主要的思路就是一点,创建一个新的栈min用来记录在当前状态下本来那个栈stk的最小值.最小值就是min栈的栈顶。

class MinStack {
public:
    stack<int> stk;
    stack<int> min;
    void push(int x) {
        stk.push(x);
        if(min.empty() || x<=min.top())
        {
            min.push(x);
        }
    }

    void pop() {
        if(min.top() == stk.top()) 
        {
            min.pop();
        }
        stk.pop();
    }

    int top() {
       return stk.top();
    }

    int getMin() {
        return min.top();
    }
};