2.辅助栈

• 2.14
  • 秒了
  • 要求不用栈实现为下

class Node {
    int val;
    int lastMin;
    Node next;
}
class MinStack {
    private Node top;
    private int min;
 
    public MinStack() {}
 
    public void push(int val) {
        if (top == null) min = val;  // 第一个元素就是最小值
        
        Node node = new Node();
        node.val = val;
        node.next = top;
        node.lastMin = min;           // 保存当前 min
        min = Math.min(min, val);     // 更新 min
        top = node;
    }
 
    public void pop() {
        min = top.lastMin;
        top = top.next;
    }
 
    public int top() {
        return top.val;
    }
 
    public int getMin() {
        return min;
    }
}

• 2.1

  • 秒了，但是 push 时，即使不是最小的，也要重新 push 一下最小值，而不是“小于栈顶就不 psuh 了”

• 1.20

  • 第二次做没那么慌了，也有点懂初始化这种操作了，具体细节看下面

• 11.18

  • 主要是栈的声明
  • 把两个栈声明在外边
  • 初始化(new栈时)在min栈放一个最大值
  • push时一块push,但min栈需要对比是否为最小值

class MinStack {
    Deque<Integer> xStack;
    Deque<Integer> MinStack;
 
    public MinStack() {
        xStack = new LinkedList<>();
        MinStack = new LinkedList<>();
        MinStack.push(Integer.MAX_VALUE);
    }
    
    public void push(int val) {
        xStack.push(val);
        MinStack.push(Math.min(val,MinStack.peek()));
    }
    
    public void pop() {
        xStack.pop();
        MinStack.pop();
        
    }
    
    public int top() {
        return xStack.peek();
    }
    
    public int getMin() {
        return  MinStack.peek();
    }
}

1. 需要在成员变量声明两个栈
2. pop时一起pop
3. Integer.MAX_VALUE
4. 需要返回值时,使用return
5. 垃圾题,搞了半天是想考辅助栈