# 155 Min Stack

stack 裡要抓 min number 也是用 stack 想效能最好

LeetCode

Design a stack that supports push, pop, top, 
and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.

實作 stack

Example:

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

怎麼解?

這題真的沒甚麼，就是複習 Stack 觀念

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.ele = [];
    this.length = 0;
    // min 也放進 stack
    this.min = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.ele.push(x);
    this.length ++;
    let min = this.getMin();
    if( min === undefined || x <= min ){
        this.min.push(x);
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    if(this.ele.length > 0){
        let val = this.ele.pop()
        this.length --;
        if( val === this.getMin() ){
            this.min.pop();
        }
    }else{
        return false;
    }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    if(this.ele.length > 0){
        return this.ele[this.length - 1]
    }else{
        return false;
    }
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.min[ this.min.length-1 ];    
};

// Call
let minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
// console.log(minStack.getMin()); 
minStack.pop();
console.log(minStack.top())
console.log(minStack.getMin())

學到什麼?

特別的是 getMin 這個 method, 一開始我是用 reduce 去遍歷一次 this.ele 取最小，但其實更好作法是把 min 也存進一個 stack 裡 !!! 所以疊在最上面一定是 最小的值