面试题 03.02

How would you design a stack which, in addition to push and pop, has a function min which returns the minimum element? Push, pop and min should all operate in 0(1) time.

Example:

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> return -3. minStack.pop(); minStack.top(); --> return 0. minStack.getMin(); --> return -2.

Solutions

• the same as problem 155 Min stack

• one stack

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> s;
    int min = INT_MAX;
    MinStack() {

    }

    void push(int x) {
        if (x <= min) {
            s.push(min);
            min = x;
        }
        s.push(x);
    }

    void pop() {
        int cur = s.top(); s.pop();
        if (cur == min) {
            min = s.top(); s.pop();
        }
    }

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

    int getMin() {
        return min;
    }
};

/**
 * 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();
 */

1. two stack

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> s, min;
    MinStack() {
        min.push(INT_MAX);
    }

    void push(int x) {
        if (x <= min.top()) {
            min.push(x);
        }
        s.push(x);
    }

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

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

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

/**
 * 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();
 */