Leetcode 155: Min Stack

https://leetcode.com/problems/min-stack/description/



Notes:

This is an interesting question.

In order to increase time complexity, we usually need to sacrifice some space.

Here I want to share two ways to solve this problem.

1): use two stacks. One is a normal stack. The second one is used to record the instant minimum only as pushing elements into the first stack.

2): use one stack only. Every time  after we push in a new element, we will push in the instant minimum first.

Let realize the first one first.

See the code below:

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
       
    }

    void push(int x) {
        sk1.push(x);
        if(sk2.empty() || sk2.top() >= x) sk2.push(x);
    }

    void pop() {
        int x = sk1.top();
        sk1.pop();
        if(x==sk2.top()) sk2.pop();
    }

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

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

private:
    stack<int> sk1, sk2;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

Now let see the second one:

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
       
    }

    void push(int x) {
        int y = sk.empty() ? x : min(x, sk.top());
        sk.push(x); 
        sk.push(y);
    }

    void pop() {
        sk.pop();
        sk.pop();
    }

    int top() {
        int x = sk.top();
        sk.pop();
        int res = sk.top();
        sk.push(x);
        return res;
    }

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

private:
    stack<int> sk;
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(x);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */