155 最小栈

一、题目

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

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

二、题解

2.1 双栈法（辅助栈）

思路：使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。 当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中； 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出； 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。

import java.util.LinkedList;
import java.util.Deque;

class MinStack {
    // 数据栈
    private Deque<Integer> dataStack;
    // 最小栈
    private Deque<Integer> minStack;

    public MinStack() {
        dataStack = new LinkedList<>();
        minStack = new LinkedList<>();
    }

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

    public void pop() {
        // 同样注意这里用 int 接收来触发自动拆箱，保证比较数值大小
        int poppedValue = dataStack.pop();
        if (poppedValue == minStack.peek()) {
            minStack.pop();
        }
    }

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

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

时间复杂度：O(1)O(1)

空间复杂度：O(n)O(n)

2.2 单栈法

实现一个单链表：让链表中的每一个节点（Node）都额外存储一个信息：当前节点及它下面所有节点中的最小值。这样每次入栈就相当于在链表头部插入一个新节点，出栈就是删除头部节点，完全不需要额外的辅助栈对象。

class MinStack {
    // 自定义一个链表节点类
    private class Node {
        int val;       // 当前节点的值
        int min;       // 从栈底到当前节点的最小值
        Node next;     // 指向下一个节点（栈中的前一个元素）

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

    // 链表的头节点，相当于栈顶
    private Node head;

    public MinStack() {
        // 初始化为空
        head = null;
    }

    public void push(int val) {
        if (head == null) {
            // 如果栈为空，当前值就是最小值
            head = new Node(val, val, null);
        } else {
            // 新节点的最小值 = Math.min(当前值, 之前的最小值)
            // 新节点的 next 指向原来的 head
            head = new Node(val, Math.min(val, head.min), head);
        }
    }

    public void pop() {
        // 移除栈顶元素，也就是把 head 指向下一个节点
        if (head != null) {
            head = head.next;
        }
    }

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

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

时间复杂度：O(1)O(1)

空间复杂度：O(n)O(n)

评论