定个小目标之刷LeetCode热题（35）

155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

今天看这道题目，如果用现有的栈实现，那么基本可以满足题目要求，但是getMin()函数需要另外实现，可以使用一个辅助栈来实现，就是辅助栈用来记录每个入栈元素对应的最小值，在入栈或者出栈时同步更新辅助栈，代码如下

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) {
        xStack.push(val);
        minStack.push(Math.min(minStack.peek(), val));
    }

    public void pop() {
        xStack.pop();
        minStack.pop();
    }

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

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

也可以不使用现有栈，使用链表也能大概实现基本功能，代码如下

class MinStack {
    // root节点用于当前栈里最小元素的值
    Node root;

    public MinStack() {
        this.root = new Node();
    }

    public void push(int val) {
        // 构造一个节点插入到root节点的后面
        Node node = new Node(val, root.next);
        // 这里把root.min赋值给node.min，是因为当需要pop的元素值为root.min时，需要把除栈顶元素最小的那个重新赋值给root.min
        node.min = root.min;
        // root的next指针直接指向node节点
        root.next = node;
        // 判断新增的节点的val是否比root.min还小
        root.min = Math.min(root.min, val);
    }

    public void pop() {
        // 记录需要移除节点的next节点
        Node cur = root.next;
        // 如果当前移除的节点为root.min则把除去当前节点的min赋值给root
        if (cur.val == root.min) {
            root.min = cur.min;
        }
        // 移除当前节点
        root.next = cur.next;
        cur.next = null;
    }

    public int top() {
        return root.next.val;
    }

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

    class Node {
        Node next;
        int min, val;

        public Node() {
            this.min = Integer.MAX_VALUE;
        }

        public Node(int val) {
            this.val = val;
        }

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

题目链接：题单 - 力扣（LeetCode）全球极客挚爱的技术成长平台

原文地址：https://blog.csdn.net/qq_45682662/article/details/140093924

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！