0155 Min Stack

• Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
• C语言解法, 栈顶始终保存着目前栈里所有元素的最小值，入栈的时候判断更新，出栈的时候不需要。
  Runtime: 32 ms, faster than 45.64% of C online submissions for Min Stack.
  Memory Usage: 14.2 MB, less than 96.77% of C online submissions for Min Stack.

typedef struct _listnode{
    int val;
    int min;
    struct _listnode* next;
}ListNode;

typedef struct {
    int len;
    ListNode* dummy;
} MinStack;

MinStack* minStackCreate(int maxSize) {
    MinStack* stk = (MinStack*)calloc(1, sizeof(MinStack));
    stk->len = maxSize;
    stk->dummy = (ListNode*)calloc(1, sizeof(ListNode));
    stk->dummy->next = NULL;
    return stk;
}

void minStackPush(MinStack* obj, int x) {
    ListNode* tp = (ListNode*)calloc(1, sizeof(ListNode));
    tp->val = x;
    /*如果不是第一个节点，且x大于目前栈里元素的最小值，则不更新*/
    if(obj->dummy->next!=NULL && x>obj->dummy->next->min)
        tp->min = obj->dummy->next->min;
    else/*其他情况就要根据栈顶的元素更新最小值*/
        tp->min = x;
    tp->next = obj->dummy->next;
    obj->dummy->next = tp;
}

void minStackPop(MinStack* obj) {
    ListNode* tp = obj->dummy->next;
    obj->dummy->next = tp->next;
    free(tp);
    tp = NULL;
}

int minStackTop(MinStack* obj) {
    return obj->dummy->next->val;
}

int minStackGetMin(MinStack* obj) {
    return obj->dummy->next->min;
}

void minStackFree(MinStack* obj) {
    ListNode* tp = obj->dummy->next;
    while(obj->dummy != NULL && tp != NULL){
        free(obj->dummy);
        obj->dummy = tp;
        tp = tp->next;
    }
    free(obj->dummy);
    free(obj);
}

• Java解法
  Runtime: 59 ms, faster than 94.49% of Java online submissions for Min Stack.
  Memory Usage: 40.6 MB, less than 68.28% of Java online submissions for Min Stack.

lass ListNode{
    public int val;
    public int min;
    public ListNode next;
    public ListNode(int _val){
        val = _val;
        next = null;
    }
}

class MinStack {
    public ListNode dummy;
    public MinStack() {
        dummy = new ListNode(0);
    }

    /*
     * @param number: An integer
     * @return: nothing
     */
    public void push(int number) {
        ListNode tr = new ListNode(number);
        if(dummy.next!=null && number>dummy.next.min)
            tr.min = dummy.next.min;
        else
            tr.min = number;
        tr.next = dummy.next;
        dummy.next = tr;
    }

    /*
     * @return: An integer
     */
    public int pop() {
        int ret = dummy.next.val;
        ListNode tp = dummy.next;
        dummy.next = tp.next;
        tp = null;
        return ret;
    }

    public int top() {
        return dummy.next.val;
    }
    
    public int getMin() {
        return dummy.next.min;
    }
}