😀前言
在日常编程中，栈是一种常见的数据结构，具有后进先出的特点。它支持基本的操作如 push（入栈）、pop（出栈）和 top（获取栈顶元素）。然而，当需要在栈中快速获取最小值时，这就成为了一个具有挑战性的任务。本文将介绍如何实现一个支持 min 函数的栈数据结构，并提供代码示例。

😀包含 min 函数的栈

题目链接

牛客网

🥰问题描述

我们需要实现一个栈结构，除了常规的栈操作外，还需要支持 min 函数，能够在 O(1) 的时间复杂度内返回栈中最小的元素。要求如下：

• push(value): 将 value 压入栈中。
• pop(): 弹出栈顶元素。
• top(): 获取栈顶元素。
• min(): 获取栈中最小元素。

所有操作都需要在常数时间内完成。我们可以通过维护一个额外的栈来解决这个问题。

😊解决思路

为了实现上述功能，我们可以使用两个栈：

1. 数据栈 (dataStack): 用于存储所有的元素。
2. 最小栈 (minStack): 用于存储当前栈中的最小值。

具体操作如下：

• Push 操作:
  • 将元素压入数据栈中。
  • 比较当前元素与最小栈栈顶的元素，将两者中较小的元素压入最小栈。
• Pop 操作:
  • 同时弹出数据栈和最小栈的栈顶元素。
• Top 操作:
  • 返回数据栈的栈顶元素。
• Min 操作:
  • 返回最小栈的栈顶元素。

通过这种方式，minStack 的栈顶元素始终是当前数据栈中的最小值，从而保证 min 函数在 O(1) 时间内获取最小元素。

😁代码实现

以下是基于上述思路的 Java 实现：

import java.util.Stack;

public class MinStack {
    private Stack<Integer> dataStack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();

    /**
     * 将一个元素推入栈中
     * @param node 元素值
     */
    public void push(int node) {
        dataStack.push(node);
        if (minStack.isEmpty() || node <= minStack.peek()) {
            minStack.push(node);
        } else {
            minStack.push(minStack.peek());
        }
    }

    /**
     * 弹出栈顶元素
     */
    public void pop() {
        dataStack.pop();
        minStack.pop();
    }

    /**
     * 获取栈顶元素
     * @return 栈顶元素
     */
    public int top() {
        return dataStack.peek();
    }

    /**
     * 获取栈中的最小元素
     * @return 最小元素
     */
    public int min() {
        return minStack.peek();
    }
}

🤗示例分析

假设我们进行如下操作序列：

假设我们进行如下操作序列：

String[] operations = {"PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"};

解释如下：

1. PSH-1: 将 -1 压入栈中。此时栈中元素为 [-1]，最小栈也为 [-1]。
2. PSH2: 将 2 压入栈中。此时栈中元素为 [2, -1]，最小栈为 [-1, -1]（因为 -1 是最小值）。
3. MIN: 获取当前最小值，即最小栈的栈顶元素 -1。
4. TOP: 获取栈顶元素，即 2。
5. POP: 弹出栈顶元素，栈中元素变为 [-1]，最小栈为 [-1]。
6. PSH1: 将 1 压入栈中。此时栈中元素为 [1, -1]，最小栈为 [-1, -1]（因为 -1 仍是最小值）。
7. TOP: 获取栈顶元素，即 1。
8. MIN: 获取当前最小值，即最小栈的栈顶元素 -1。

😄总结

通过维护一个额外的最小栈，我们可以在 O(1) 的时间复杂度内获取栈中最小值，且所有操作的空间复杂度为 O(n)。这种方法不仅简单易实现，而且高效，适用于各种需要快速获取最小值的场景。希望这篇文章能帮助你更好地理解和实现包含最小函数的栈数据结构。