Leetcode Algorithms -- Min Stack

Min Stack (Easy)

Description

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
getMin() – Retrieve the minimum element in the stack.

Analysis

太sxbk了= =。。用两个vector也mle。。用stack就过了。
而且要维护一个min的stack。不能每一位的min值都插入进去，否则mle。
可以考虑仅当<=的情况下插入，因为大于的情况不会影响值得输出。

My Solution

//C++
class MinStack {
    stack<int> st;
    stack<int> minx;
public:
    void push(int x) {
        if(st.empty()){
            st.push(x);
            minx.push(x);
        }
        else{
            if(x<=minx.top())
                minx.push(x);
            st.push(x);
        }

    }

    void pop() {
        if(!st.empty()){
            if(st.top()==minx.top())
                minx.pop();
            st.pop();
        }
    }

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

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