155. 最小栈

155. 最小栈

• Java，辅助栈，与数据栈同步版本

  // 使用辅助栈记录最小值
  // 入栈操作：如果 x 比辅助栈顶小则将 x 推入辅助栈
  // 如果 x 比辅助栈顶大则在辅助栈 push 自身的栈顶，因为辅助栈的长度要与数据栈同步
  // pop 操作时直接将两个栈同时 pop
  class MinStack {
    private Deque<Integer> data;
    private Deque<Integer> min;
    public MinStack() {
        data = new LinkedList<>();
        min = new LinkedList<>();
    }
    public void push(int x) {
        data.push(x);
        if (min.isEmpty() || x < min.peek()) {
            min.push(x);
        } else {
            min.push(min.peek());
        }
    }
    public void pop() {
        data.pop();
        min.pop();
    }
    public int top() {
        return data.peek();
    }
    public int getMin() {
        return min.peek();
    }
  }

• Java，辅助栈，与数据栈非同步版本

  // 使用辅助栈记录最小值
  // 入栈操作：如果 x 小于等于辅助栈顶才将 x 推入辅助栈，
  // 出栈操作：如果数据栈顶与辅助栈顶相同才将辅助栈弹出一个元素
  class MinStack {
    private Deque<Integer> data;
    private Deque<Integer> min;
    public MinStack() {
        data = new LinkedList<>();
        min = new LinkedList<>();
    }
    public void push(int x) {
        data.push(x);
        if (min.isEmpty() || x <= min.peek()) {
            min.push(x);
        }
    }
    public void pop() {
        if (data.pop().equals(min.peek())) {
            min.pop();
        }
    }
    public int top() {
        return data.peek();
    }
    public int getMin() {
        return min.peek();
    }
  }

• Java 使用辅助类记录最小值

  // 使用一个类记录每个节点的最小值，在push操作的时候缓存这个最小值
  // 其它操作只要直接返回结果即可
  class MinStack {
  
    private Deque<MinStackNode> data;
  
    public MinStack() {
        data = new LinkedList<>();
    }
  
    public void push(int x) {
        MinStackNode node = new MinStackNode(x, x);
        if (!data.isEmpty()) {
            if (x < data.peek().min) {
                node.min = x;
            } else {
                node.min = data.peek().min;
            }
        }
        data.push(node);
    }
  
    public void pop() {
        data.pop();
    }
  
    public int top() {
        return data.peek().val;
    }
  
    public int getMin() {
        return data.peek().min;
    }
  
    private static class MinStackNode {
        public int val;
        public int min;
  
        public MinStackNode(int val, int min) {
            this.val = val;
            this.min = min;
        }
    }
  }