曾续缘

切换主题

大家好！我是曾续缘😺

今天是《LeetCode 热题 100》系列

发车第 70 天

栈第 2 题

❤️点赞 👍 收藏 ⭐再看，养成习惯

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

实现 MinStack 类:

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

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

  • -231 <= val <= 231 - 1
  • pop、top 和 getMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 3 * 104 次
难度：💖💖

解题方法 ​

首先，我们要理解题目中的四个基本操作：push、pop、top 和 getMin。

  1. push(val)：这个操作相当于把一个新元素val放到栈顶，也就是栈的最上面。

  2. pop()：这个操作要从栈顶移除元素，也就是把最上面的元素扔掉。

  3. top()：这个操作要获取栈顶的元素，但不把栈顶元素移除。

  4. getMin()：这个操作要获取栈中当前的最小元素。

在普通的栈中，我们只能通过遍历整个栈来找到最小值，这样会花费O(n)的时间。但题目要求我们在常数时间内找到最小值，所以我们需要一个额外的数据结构来帮助我们快速找到最小值。

这个额外的数据结构我们叫做“最小值栈”，简称mn。mn的作用是记录每个阶段栈中的最小值。

1. MinStack() 初始化 ​

java
class MinStack {
    private Stack<Integer> mn; // 最小值栈
    private Stack<Integer> common; // 普通栈
    public MinStack() {
        mn = new Stack<>(); // 初始化最小值栈
        common = new Stack<>(); // 初始化普通栈
    }
    // ... 其他方法
}

2. push(val) 操作 ​

当我们向栈中添加一个新的元素val时：

  • 首先，我们要检查这个新加入的元素val是否比当前最小值还要小。
  • 如果val比当前最小值还要小，那我们就要把当前的最小值替换成val。
  • 然后，我们把val加入到普通栈中。
java
public void push(int val) {
    if (mn.isEmpty() || val <= mn.peek()) { // 检查val是否小于等于当前最小值
        mn.push(val); // 如果是，更新最小值栈的最顶端为val
    }
    common.push(val); // 不管怎样，都要把val加入到普通栈中
}

3. pop() 操作 ​

当我们从栈中移除一个元素时：

  • 我们首先要确认，如果要移除的元素正好是最小值，那就同时从两个栈中移除。
  • 如果不是最小值，那就只从普通栈中移除。
java
public void pop() {
    if (common.peek().equals(mn.peek())) { // 如果栈顶元素就是最小值
        common.pop(); // 从普通栈中移除
        mn.pop(); // 从最小值栈中移除
    } else {
        common.pop(); // 如果不是最小值，只从普通栈中移除
    }
}

4. top() 操作 ​

这个操作很简单，我们只需要返回普通栈的栈顶元素即可，因为普通栈的栈顶元素就是当前栈的最上面一个元素。

java
public int top() {
    return common.peek(); // 返回普通栈的栈顶元素
}

5. getMin() 操作 ​

这个操作要获取当前栈中的最小值，由于我们已经有了一个专门记录最小值的栈mn，所以只需要返回mn的栈顶元素即可。

java
public int getMin() {
    return mn.peek(); // 返回最小值栈的栈顶元素
}

通过以上步骤，我们就可以实现一个能在常数时间内检索到最小元素的栈——MinStack。

Code ​

查看代码
java
class MinStack {
    private Stack<Integer> mn;
    private Stack<Integer> common;

    public MinStack() {
        mn = new Stack<>();
        common = new Stack<>();
    }

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

    public void pop() {
        if (common.peek().equals(mn.peek())) {
            common.pop();
            mn.pop();
        } else {
            common.pop();
        }
    }

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

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