155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

思路一：辅助栈

class MinStack {
    stack<int> x_stack;
    stack<int> min_stack;
public:
    MinStack() {
        min_stack.push(INT_MAX);
    }
    
    void push(int x) {
        x_stack.push(x);
        min_stack.push(min(min_stack.top(), x));
    }
    
    void pop() {
        x_stack.pop();
        min_stack.pop();
    }
    
    int top() {
        return x_stack.top();
    }
    
    int getMin() {
        return min_stack.top();
    }
};

思路二：LRU

class node{
public:
    int val;
    node* next;
    node* pre;
    node(int v){
        this->val = v;
    }
};

class doublelist{
private:
    node* head;
    node* r;
public:
    doublelist(){
        head = new node(INT_MIN);
        r = new node(INT_MAX);
        head->next = r;
        r->pre = head;
    }
    void add(node* n){
        node* p = head->next;
        while(n->val > p->val){
            p = p->next;
        }
        node* pre = p->pre;
        pre->next = n;
        n->pre = pre;
        n->next = p;
        p->pre = n;
    }
    void remove(node *n){
        n->pre->next = n->next;
        n->next->pre = n->pre;
    }
    int get_head(){
        node* min = head->next;
        return min->val;
    }
};

class MinStack {
private:
    stack<node*> sta;
    doublelist cache;
public:
    MinStack() {

    }
    
    void push(int val) {
        node* cur = new node(val);
        sta.push(cur);
        cache.add(cur);
    }
    
    void pop() {
        node* cur = sta.top();
        sta.pop();
        cache.remove(cur);
    }
    
    int top() {
        node* cur = sta.top();
        return cur->val;
    }
    
    int getMin() {
        return cache.get_head();
    }
};