本文共 1036 字，大约阅读时间需要 3 分钟。

实现一个支持min()功能的堆栈

问题描述

我们需要设计一个堆栈数据结构，支持push、pop和min三个操作，且每个操作的时间复杂度为O(1)。这些操作分别是将元素压入堆栈、弹出堆栈顶部的元素以及获取堆栈中的最小值。为了实现这一目标，我们需要巧妙地利用堆栈的特性，同时维护一个辅助结构来记录最小值。

方法一：使用两个堆栈

我们可以使用两个堆栈来实现这个目标。主要堆栈（m1）负责存储所有元素，辅助堆栈（m2）负责存储当前堆栈中的最小值。具体实现如下：

这种方法确保了在push和pop操作时，辅助堆栈m2始终记录当前堆栈中的最小值，从而实现了O(1)时间复杂度的min操作。

方法二：使用最小值变量

另一种实现方式是使用一个变量mn来记录当前堆栈中的最小值。具体实现如下：

这种方法通过维护一个辅助变量来记录最小值，避免了额外的堆栈操作，实现了O(1)时间复杂度的min操作。

边界条件与测试

在实际应用中，需要考虑以下边界条件：

通过上述两种方法，我们可以实现一个支持push、pop和min操作的堆栈，且每个操作的时间复杂度均为O(1)。选择哪种方法取决于具体需求和实现偏好。

示例测试

• push(1)pop()：返回1
• push(2)push(3)min()：返回2
• push(1)min()：返回1

这些测试用例验证了两种方法的正确性，确保在各种情况下min操作返回堆栈中的最小值。

结论

通过以上分析，我们可以明确选择一种适合的实现方法，并确保在各种测试用例下都能正确工作。这种设计既简洁又高效，是解决类似问题的典型方法。