155. Min Stack

一个栈，比两个栈节省一点空间

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

    }

    void push(int x) {
        if (x <= mn) { // 当需要修改当前最小值时，把旧的最小值压栈，然后修改，这里必须包含等于mn的情况，否则pop时无法判断栈顶下面是否压栈的是旧的mn还是另外一个数
            s.push(mn); // 压栈旧的最小值
            mn = x; // 更新最小值
        }
        s.push(x);
    }

    void pop() {
        int t = s.top(); s.pop();
        if (t == mn) { // 当要出栈的数跟当前最小值一样时，下一个栈顶的数一定是一个旧的最小值，用这个旧的最小值来给mn赋值
            mn = s.top(); s.pop();
        }
    }

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

    int getMin() {
        return mn;
    }

    stack<int> s;
    int mn = INT_MAX;
};

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

两个栈，一个正常栈维护数，一个最小值栈维护当前的最小值

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

    }

    void push(int x) {
        s.push(x);
        m.push(m.empty() ? x : min(m.top(), x));
    }

    void pop() {
        s.pop();
        m.pop();
    }

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

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

    stack<int> s;
    stack<int> m;
};

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

min queue
单调deque，最省空间
amortized O(1) time

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

    }

    void push(int x) {
        while (!m.empty() && m.back() > x) {
            m.pop_back();
        }
        m.push_back(x);
        q.push(x);
    }

    void pop() {
        if (!m.empty() && q.front() == m.front()) {
            m.pop_front();
        }
        q.pop();
    }

    int front() {
        return q.front();
    }

    int getMin() {
        return m.front();
    }

    queue<int> q;
    deque<int> m;
};

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

利用232. Implement Queue using Stacks

struct Queue {
    void push(int x) {
        back.push(x);
    }

    int pop() {
        rearrange();
        return front.pop();
    }

    int getMin() {
        int res = INT_MAX;
        if (!front.empty()) {
            res = min(res, front.getMin());
        }
        if (!back.empty()) {
            res = min(res, back.getMin());
        }
        return res;
    }

    void rearrange() {
        if (front.empty()) {
            while (!back.empty()) {
                front.push(back.pop());
            }
        }
    }

    Stack back, front;
};