设计一个支持 O(1) 时间和 O(1) 额外空间 getMin() 的栈

引言

栈是计算机科学和软件工程中常用的基本数据结构。它们使用后进先出 (LIFO) 原则，这意味着最后插入的元素最先被移除。传统的栈解决方案在另一方面需要有效地获取最小元素。在本文中，我们将探讨一种创建栈的创新方法，该方法可以在不占用栈本身之外的额外空间的情况下，以恒定的时间检索最小元素。

理解问题

目标是创建一个栈数据结构，它不仅支持 push、pop 和 peek 等典型栈操作，而且还能在常数时间内（即 O(1)）高效地支持检索最小元素。此外，我们希望在不增加任何额外空间复杂性的情况下实现这一点，保持 O(1) 的额外空间。

操作

Push(x)：此操作将元素 x 添加到栈顶，并确保栈的最小元素得到正确更新。

Pop()：此方法从栈中移除顶部元素。如果顶部元素是最小元素，它也应该从辅助栈中移除。

Top()：此方法在不删除的情况下检索栈顶元素。

getMin()：此方法返回当前栈中的最小元素。

以下是每个过程如何工作的详细说明

Push(x)

• 将元素 x 添加到主栈。
• 如果辅助栈为空，或者 x 小于或等于辅助栈的顶部元素，则将 x 推送到辅助栈。
• 否则，复制辅助栈的顶部元素并将其再次推送到辅助栈。

Pop()

• 从主栈中移除顶部元素。
• 如果弹出的元素与辅助栈的顶部元素相同，则同时弹出两者。

Top()

• 在不删除的情况下返回主栈的顶部元素。

getMin()

• 返回辅助栈的顶部元素，它对应于主栈中的最小元素。

实现支持 O(1) 时间和 O(1) 额外空间获取最小值的栈的策略是巧妙地利用一个辅助栈来跟踪每个给定主栈状态下的最小元素。以下是该方法的详细步骤说明

方法 1：主栈（或称主栈）

• 此栈保留被推入其中的元素。
• 它支持常见的栈操作，包括 push、pop 和 peek。

方法 2：辅助栈（最小栈）

• 此栈是对主栈的补充。
• 它在任何给定时间跟踪主栈中的最小元素。
• 当一个元素被推入主栈时，我们将其与辅助栈的顶部元素进行比较。
• 如果元素小于或等于辅助栈的顶部元素，则将其推送到辅助栈。
• 如果元素更大，我们通过再次将其推入来复制辅助栈的顶部元素。
• 这确保了辅助栈始终具有对应于主栈当前状态的最小元素。

实施

输出

说明

• 在此方法中，每个栈节点 (StackNode) 存储两类信息：数据和该节点的值。我们也可以将其修改为存储数据以及当前栈中的最小值。
• 如果在 push() 操作期间栈为空，则数据被设置为新节点的最小值。否则，它被设置为当前数据与前一个最小值 (top.min) 中的较小值。
• pop()、top() 和 isEmpty() 函数在栈实现中正常工作。
• getMin() 函数返回顶部节点的最小值，其检索时间复杂度为 O(1)。