Leetcode Hot100 61-65

Source

法一:使用辅助栈

一个栈正常存,另一个存最小值

class MinStack {

    Deque<Integer>stack;
    Deque<Integer>minstack;
    public MinStack() {
        stack = new LinkedList<>();
        minstack = new LinkedList<>();

    }

    public void push(int val) {
        stack.push(val);
        if(minstack.isEmpty()||val <= minstack.peek()){
            minstack.push(val);
        }
    }

    public void pop() {
        Integer pop = stack.pop();
        if(pop.equals(minstack.peek())){
            minstack.pop();
        }
    }

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

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

法二:创建新的Node节点,Node节点包括val和min

class MinStack {
    private  static class Node{
        int value;
        int min;
        Node next;

        Node(int x,int min){
            this.value = x;
            this.min = min;
            next = null;
        }
    }
    private Deque<Node>stack;
    public MinStack() {
        stack  = new LinkedList<>();
    }

    public void push(int val) {
        if(stack.isEmpty()){
            stack.push(new Node(val,val));
        }
        else{
            stack.push(new Node(val,Math.min(stack.peek().min,val)));
        }
    }

    public void pop() {
        stack.pop();
    }

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

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

自己实现栈,可以用单链表的头插法

class MinStack {
    class Node{
        int value;
        int min;
        Node next;

        Node(int x, int min){
            this.value=x;
            this.min=min;
            next = null;
        }
    }
    Node head;
    //每次加入的节点放到头部
    public void push(int x) {
        if(null==head){
            head = new Node(x,x);
        }else{
            //当前值和之前头结点的最小值较小的做为当前的 min
            Node n = new Node(x, Math.min(x,head.min));
            n.next=head;
            head=n;
        }
    }

    public void pop() {
        if(head!=null)
            head =head.next;
    }

    public int top() {
        if(head!=null)
            return head.value;
        return -1;
    }

    public int getMin() {
        if(null!=head)
            return head.min;
        return -1;
    }
}

作者:windliang
链接:https://leetcode.cn/problems/min-stack/solutions/42521/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-38/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。