P17 带有 min 函数的栈

描述#

这个题目说的是，你要实现一个栈，除了提供 push，pop，top 等常用函数，还需要提供一个函数在 O(1) 时间内取得这个栈里的最小元素。

代码#

public class AlgoCasts {

  class MinStackWithTwoStack {

    private Stack<Integer> stack = new Stack<>();
    private Stack<Integer> min = new Stack<>();

    public void push(int x) {
      stack.push(x);
      if (min.isEmpty() || x <= getMin()) min.push(x);
    }

    public void pop() {
      if (stack.peek() == getMin()) min.pop();
      stack.pop();
    }

    public int top() {
      return stack.peek();
    }

    public int getMin() {
      return min.peek();
    }
  }

  class MinStackWithLinkedList {

    private class Node {
      int val;
      Node next;

      Node(int val, Node next) {
        this.val = val;
        this.next = next;
      }
    }

    private Node head = null;
    private int min = Integer.MAX_VALUE;

    public void push(int x) {
      if (x <= min) {
        head = new Node(min, head);
        min = x;
      }
      head = new Node(x, head);
    }

    public void pop() {
      if (head.val == min) {
        min = head.next.val;
        head = head.next.next;
      } else {
        head = head.next;
      }
    }

    public int top() {
      return head.val;
    }

    public int getMin() {
      return min;
    }
  }

}