Min Stack

min stack.

Discussion

除了一个栈存输入数据，再用一个栈维护最小值，这个最小栈

• 只有当新来的值<=当前值的时候才插入
• 只有当pop出的值 == 当前值的时候才pop

Solution

class MinStack {
public:
    void push(int x) {
        if(min_stack.empty() || x <= getMin()) {
            min_stack.emplace(x);
        }
        input.emplace(x);
    }

    void pop() {
        if(input.top() == getMin()) {
            min_stack.pop();
        }
        input.pop();
    }

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

    int getMin() {
        return min_stack.top();
    }
private:
    stack<int> input;
    stack<int> min_stack;
};

Follow up:

saveing space的解法， 只用一个栈，保存的是difference

class MinStack {
public:
    MinStack() {
        // do initialization if necessary
    }

    void push(int number) {
        if (elements_.empty()) {
            elements_.emplace(0);
            stack_min_ = number;
        } else {
            elements_.emplace(number - stack_min_);
            if (number < stack_min_) {
                stack_min_ = number; // Update min.
            }
        }
    }
    int top() {
        int diff = elements_.top();
        int cur_min = stack_min_;
        if (diff < 0) {
            cur_min -= diff; // Restore previous min.
        }
        return cur_min + diff;
    }
    void pop() {
        int diff = elements_.top();
        elements_.pop();
        if (diff < 0) {
            stack_min_ -= diff; // Restore previous min.
        }
        stack_min_ + diff;
    }

    int getMin() {
        return stack_min_;
    }
private:
    stack<int> elements_;
    int stack_min_;
};

上面这个解法在不能处理INT_MIN, INT_MAX的情况，在leetcode上会溢出。

下面这个解法也是用一个stack，但是最小值是重复存了，所以可以用一个栈。

class MinStack {
    int min=Integer.MAX_VALUE;
    Stack<Integer> stack = new Stack<Integer>();
    public void push(int x) {
       // only push the old minimum value when the current 
       // minimum value changes after pushing the new value x
        if(x <= min){          
            stack.push(min);
            min=x;
        }
        stack.push(x);
    }

    public void pop() {
       // if pop operation could result in the changing of the current minimum value, 
       // pop twice and change the current minimum value to the last minimum value.
        if(stack.peek()==min) {
            stack.pop();
            min=stack.peek();
            stack.pop();
        }else{
            stack.pop();
        }
        if(stack.empty()){
            min=Integer.MAX_VALUE;
        }
    }

    public int top() {
        return stack.peek();
    }

    public int getMin() {
        return min;
    }
}