Leetcode-剑指Offer30

保存差值栈

剑指 Offer 30. 包含min函数的栈

min_x: 栈中最小值
栈diff_stack: 元素与最小值的差

如果diff_stack.top()<0,栈顶元素位min_x,否则栈顶元素为min_x+diff_stack.top().
push方法中先计算diff再更新min_x是建立之前栈最小值与当前栈最小值的联系.
需要注意的是两个int类型数相减可能越界,需要用long long保存差值.

class MinStack {
public:
    stack<long long> diff_stack;
    int min_x = 0;
    MinStack() {

    }
    
    void push(int x) {
        if(diff_stack.size()==0){
            diff_stack.push(0L);
            min_x = x;
        }else{
            long long diff = (long long)x-min_x;
            diff_stack.push(diff);
            if(diff<0) min_x = x;
        }
    }
    
    void pop() {
        if(diff_stack.top()<0) min_x = min_x-diff_stack.top();
        diff_stack.pop();
    }
    
    int top() {
        return diff_stack.top()<0?min_x:diff_stack.top()+min_x;
    }
    
    int min() {
        return min_x;
    }
};