每日力扣：155. 最小栈，用双栈、双向链表分别实现

约定不等于承诺〃 2022-02-25 01:38 126阅读 0赞

package com.sample.suncht.algo;
    
    import java.util.Stack;
    
    /**
     *
     * 155. 最小栈
     *
     * 设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
     *
     * push(x) -- 将元素 x 推入栈中。
     * pop() -- 删除栈顶的元素。
     * top() -- 获取栈顶元素。
     * getMin() -- 检索栈中的最小元素。
     * 示例:
     *
     * MinStack minStack = new MinStack();
     * minStack.push(-2);
     * minStack.push(0);
     * minStack.push(-3);
     * minStack.getMin();   --> 返回 -3.
     * minStack.pop();
     * minStack.top();      --> 返回 0.
     * minStack.getMin();   --> 返回 -2.
     * 
     * 双栈、链表分别实现，链表效率比双栈高些
     *
     */
    public class MinStack155 {
        /**
         * 双栈实现
         * 执行用时：122 ms
         */
        static class MinStack {
            Stack<Integer> stack = new Stack<>();
            Stack<Integer> minStack = new Stack<>();
            public MinStack() {
    
            }
    
            /**
             * 将元素 x 推入栈中
             * @param x
             */
            public void push(int x) {
                stack.push(x);
    
                if(minStack.size() > 0) {
                    int min = minStack.peek();
                    minStack.push(min > x ? x : min);
                } else {
                    minStack.push(x);
                }
            }
    
            /**
             * 删除栈顶的元素。
             */
            public void pop() {
                stack.pop();
                minStack.pop();
            }
    
            /**
             * 获取栈顶元素。
             * @return
             */
            public int top() {
                return stack.peek();
            }
    
            public int getMin() {
                return minStack.peek();
            }
        }
    
        /**
         * 双向链表实现
         * 执行用时 : 101 ms,
         */
        static class MinStack2 {
            private Node top;
            private Node tail;
    
            public MinStack2() {
            }
    
            /**
             * 将元素 x 推入栈中
             * @param x
             */
            public void push(int x) {
                if(top == null && tail == null) {
                    Node node = new Node(x, x);
                    top = node;
                    tail = node;
                } else {
                    Node node = new Node(x, top.getMinValue() > x ? x : top.getMinValue());
    
                    Node topNode = top;
                    node.setPre(topNode);
                    topNode.setNext(node);
    
                    top = node;
                }
            }
    
            /**
             * 删除栈顶的元素。
             */
            public void pop() {
                if(top == null) {
                    throw new RuntimeException("can't empty");
                }
                Node topNode = top;
                if(topNode.getPre() == null) {
                    top = null;
                    tail = null;
                } else if(topNode.getPre() == tail) {
                    top = tail;
                    top.setNext(null);
                } else {
                    top = topNode.getPre();
                    top.setNext(null);
                }
    
                topNode = null;
            }
    
            /**
             * 获取栈顶元素。
             * @return
             */
            public int top() {
                if(top == null) {
                    throw new RuntimeException("can't empty");
                }
                return top.getValue();
            }
    
            public int getMin() {
                if(top == null) {
                    throw new RuntimeException("can't empty");
                }
                return top.getMinValue();
            }
        }
    
        static class Node {
            private Node next;
            private Node pre;
            private int value;
            private int minValue;
    
            public Node(int value, int minValue) {
                this.value = value;
                this.minValue = minValue;
            }
    
    
            public Node getNext() {
                return next;
            }
    
            public void setNext(Node next) {
                this.next = next;
            }
    
    
            public int getValue() {
                return value;
            }
    
            public void setValue(int value) {
                this.value = value;
            }
    
            public int getMinValue() {
                return minValue;
            }
    
            public void setMinValue(int minValue) {
                this.minValue = minValue;
            }
    
            public Node getPre() {
                return pre;
            }
    
            public void setPre(Node pre) {
                this.pre = pre;
            }
    
        }
    }