leetcode:最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["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.

字节一面 要求额外O（1）辅助空间

class MinStack {
    Stack<Long> st; // 存储当前值相对于minVal的偏移量
    long minVal; // 存储最小值

    public MinStack() {
        st = new Stack<>();
        minVal = 0L;
    }
    
    public void push(int val) {
        if (st.isEmpty()) { // 如果栈为空，则minVal为当前值，偏移量为0
            st.push(0L);
            minVal = (long)val;
        } else { // 如果栈不为空
            long diff = val - minVal; // 计算当前值与minVal的偏移量
            st.push(diff); // 入栈偏移量
            if (diff < 0) minVal = val; // 更新最小值，用当前val更新minVal
        }
    }
    
    public void pop() {
        long diff = st.pop(); // 出栈偏移量
        // 如果偏移量为负数，则minVal为更新过后的最小值，需要将minVal更新为前一个最小值
        // 根据push时的式子 diff = val - minVal，有minVal = val - diff，其中val则为当前的minVal
        if (diff < 0) minVal -= diff;
    }
    
    public int top() {
        long diff = st.peek(); // 获取偏移量
        // 如果为正数，则 当前值 = minVal + 偏移量
        if (diff > 0) return (int)(minVal + diff);
        // 如果为负数，则 当前值 = minVal
        return (int)minVal;
    }
    
    public int getMin() {
        return (int)minVal;
    }
}