leetcode-155 最小棧

設計一個支援 push，pop，top 操作，并能在常數時間内檢索到最小元素的棧。

• push(x) – 将元素 x 推入棧中。
• pop() – 删除棧頂的元素。
• top() – 擷取棧頂元素。
• getMin() – 檢索棧中的最小元素。

示例：

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); --> 傳回 -3.

minStack.pop();

minStack.top(); --> 傳回 0.

minStack.getMin(); --> 傳回 -2.

方法一：使用輔助棧

使用輔助棧來存儲目前資料棧的最小元素，即插入元素時 同時維護資料棧和輔助棧，資料棧正常放入元素；輔助棧的棧頂則儲存目前資料棧中最小的元素即可

實作如下：

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        
    }
    
    void push(int x) {
        data.push(x);

        //維護輔助棧
        //如果目前元素大小 小于輔助棧頂元素，則将目前元素放入輔助棧中
        if (min_stack.empty()) {
            min_stack.push(x);
        } else {
            if (x < min_stack.top()) {
                min_stack.push(x);
            } else {
                min_stack.push(min_stack.top());
            }
        }
    }
    
    void pop() {
        data.pop();
        min_stack.pop();
    }
    
    int top() {
        return data.top();
    }
    
    int getMin() {
        return min_stack.top();
    }
private:
    stack<int> min_stack;
    stack<int> data;
};      

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
        
    }
    
    void push(int x) {
        if(data.empty()){
            data.push(x);
            data.push(x);
        } else {
            if (x >= data.top()) {
                int tmp = data.top();
                data.push(x);
                data.push(tmp);
            } else {
                data.push(x);
                data.push(x);
            }
        }
    }
    
    void pop() {
        data.pop();
        data.pop();
    }
    
    //傳回時需先儲存棧頂的最小元素
    int top() {
        int tmp = data.top();
        data.pop();
        
        int result = data.top();
        data.push(tmp);
        return result;
    }
    
    int getMin() {
        return data.top();
    }
private:
    stack<int> data;
};