Leetcode: 155. 最小棧

描述

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

push(x) —— 将元素 x 推入棧中。

pop() —— 删除棧頂的元素。

top() —— 擷取棧頂元素。

getMin() —— 檢索棧中的最小元素。

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/min-stack

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

示例

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

輸出：
[null,null,null,null,-3,null,0,-2]

解釋：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 傳回 -3.
minStack.pop();
minStack.top();      --> 傳回 0.
minStack.getMin();   --> 傳回 -2.

來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/min-stack
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
           

class MinStack {
public:
    stack<int> s;
    stack<int> help;
    /** initialize your data structure here. */
    MinStack() {
        help.push(INT_MAX);
    }
    
    void push(int x) {
        if (x <= help.top()) {
            help.push(x);
        }
        s.push(x);

    }
    
    void pop() {
        if (s.top() == help.top()){
             s.pop();
             help.pop();
        } else
            s.pop();
    }
    
    int top() {
        return s.top();
    }
    
    int getMin() {
        return help.top();
    }
};

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

要點

每次最小值要變化，就把對應的x加入到輔助棧中

删除時分資料棧頂元素和輔助棧頂元素相同或者不同兩種情況，相同時兩個棧都删除元素，不同時隻删除資料棧元素