小学生都能看懂的题解 | #包含min函数的栈#

想象一下，你有一个装玩具的盒子，你可以把玩具放进去（压入），也可以拿出来（弹出）。现在，我们要做一个特殊的盒子，它不仅能告诉你最后一个放进去的玩具是什么（栈顶），还能随时告诉你盒子里最小的玩具是什么（最小值）。

特殊盒子的工作方式：

1. 放玩具（压入）：
1. 当你放一个新的玩具进去时，我们会记住它是不是比现在盒子里最小的玩具还要小。
2. 如果是，那么我们会把这个新玩具的信息记两遍：
1. 一次放在正常的地方，一次放在特别的地方用来记住当前最小的玩具。
2. 拿玩具（弹出）：
1. 当你拿出一个玩具时，如果这个玩具是最小的那个，那么我们也要从记住最小玩具的地方把它去掉。
3. 看最后一个放进去的玩具（栈顶）：
1. 这个很简单，就是看看最上面的一个玩具是什么。
4. 找最小的玩具（最小值）：
1. 我们总是记得当前最小的玩具是什么，所以这个也很容易做到。

示例：

假设我们的特殊盒子开始是空的。

• 你放了一个 -1 进去。这时，最小的是 -1，也是最后放进去的一个。
• 再放一个 2 进去。这时，最后放进去的是 2，但是最小的还是 -1。
• 问最小的玩具是什么？答案是 -1。
• 看看最后放进去的玩具是什么？答案是 2。
• 把 2 拿出来。现在最小的还是 -1，最后放进去的也是 -1。
• 放一个 1 进去。这时，最后放进去的是 1，但是最小的还是 -1。
• 再看看最后放进去的玩具是什么？答案是 1。
• 最后再问一次最小的玩具是什么？答案还是 -1。

这就是一个简单的特殊盒子（栈）工作的方式，它可以让你很快知道最小的玩具是什么。

现在来看看简单的代码实现：

import java.util.Stack;

public class MinStack {
	//定义两个盒子
    private Stack<Integer> stack;
	//放最小的玩具
    private Stack<Integer> minStack;

    public MinStack() {
        this.stack = new Stack<>();
        this.minStack = new Stack<>();
    }

    // 放入玩具
    public void push(int x) {		
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        }
        stack.push(x);
    }

    // 取出玩具
    public int pop() {
        int popped = stack.pop();
        if (!minStack.isEmpty() && popped == minStack.peek()) {
            minStack.pop();
        }
        return popped;
    }

    // 查看最后放的玩具
    public int top() {
        return stack.peek();
    }

    // 查看最小的玩具
    public int min() {
        return minStack.peek();
    }
}

如果这篇文章对你有帮助，请点个免费的赞👍，让它能够帮助更多的人。