算法刷题：递归、栈、队列（8.29，持续更）

coding now / 2023-08-30 / 原文

汉诺塔问题
最小栈

最小栈
- 额外空间\(O(N)\)
  - 辅助栈解法
  - 双值域节点链表解法
- 无额外空间
  - 差分解法

最小栈

额外空间\(O(N)\)

辅助栈解法

class MinStack {
    Deque<Integer> xStack;
    Deque<Integer> minStack;
    public MinStack() {
        xStack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }
    
    public void push(int val) {
        int x = minStack.peek();
        xStack.push(val);
        minStack.push(x < val ? x:val);
    }
    
    public void pop() {
        minStack.pop();
        xStack.pop();
    }
    
    public int top() {
        return xStack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

双值域节点链表解法

class MinStack {
    class Node{
        int val;
        int min;
        Node next;
        public Node(){
        }
        public Node(int val, int min, Node next){
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }
    Node head;
    public MinStack(){
    }
    public void push(int val){
        if(head == null){
            head = new Node(val, val, null);
        } else {
            Node cur = new Node(val, (val < head.min?val:head.min), head);
            head = cur;
        }
    }
    public void pop(){
        head = head.next;
    }
    public int top(){
        return head.val;
    }
    public int getMin(){
        return head.min;
    }
 
}