[LeetCode] 155. Min Stack

幾百年沒有更新Blog了

前幾天看到這題就順手寫了一下

用兩個stack的作法好像還蠻簡單的

但只用一個stack做就蠻炫的，discussion上有靠diff的方式只花了一個stack

簡單來說大概就是在遇到更小data push的時候更新min

pop掉的時候在用diff回到先前的 min

class MinStack {
public:
    /** initialize your data structure here. */
    long min;
    stack<long> my_stack;
    
    MinStack() {
    
    }
    
    void push(int x) {
        if(this->my_stack.empty()) {
            min = x;
            my_stack.push(0);
        }
        else
        {
            my_stack.push(x-min);
            if(x<min) min = x;
        }
    }
    
    void pop() {
        if(this->my_stack.top() < 0)
            this->min -= this->my_stack.top();
        this->my_stack.pop();
    }
    
    int top() {
        if(this->my_stack.top() > 0)
            return this->my_stack.top() + this->min;
        else
            return this->min;
    }
    
    int getMin() {
        return this->min;
    }
};