DEV Community
·
最小栈/队列
💡
原文英文，约600词，阅读约需2分钟。
📝
内容提要
修改后的栈通过在每个元素中存储当前最小值，实现了O(1)时间复杂度的最小值查询。入栈时比较新元素与当前最小值，出栈时直接移除顶部元素，确保高效处理频繁的最小值查询。这种设计在竞争编程和实时系统中非常实用。
🎯
关键要点
-
栈是一种线性数据结构，仅从顶部添加或移除元素。
-
传统栈无法高效跟踪最小元素，查找最小值的时间复杂度为O(n)。
-
在传统栈中，移除元素会导致丢失最小值的信息。
-
修改后的栈通过在每个元素中存储当前最小值，实现了O(1)时间复杂度的最小值查询。
-
每个栈元素存储为一对：元素本身和该元素以下的最小值。
-
入栈时比较新元素与当前最小值，出栈时直接移除顶部元素。
-
所有操作（入栈、出栈和查找最小值）均在O(1)时间内完成，效率高。
-
修改后的栈仅需为每个元素存储一个额外的整数（最小值），确保空间效率。
-
该设计在竞争编程和实时系统中非常实用，能够快速解决频繁的最小值查询。
-
修改后的栈在性能和空间效率之间取得了良好的平衡。
❓
延伸问答
什么是最小栈，它是如何工作的？
最小栈是一种修改后的栈，通过在每个元素中存储当前最小值，实现O(1)时间复杂度的最小值查询。每个元素存储为一对：元素本身和该元素以下的最小值。
传统栈在查找最小值时有什么缺陷？
传统栈无法高效跟踪最小元素，查找最小值的时间复杂度为O(n)，并且移除元素会导致丢失最小值的信息。
如何在最小栈中执行入栈操作？
在入栈时，比较新元素与当前最小值，将较小的值作为新的最小值与元素一起存储。
最小栈的出栈操作是怎样的？
出栈时，直接移除顶部元素，新的最小值已经在下一个顶部元素的第二个值中跟踪。
最小栈在性能和空间效率上有什么优势？
最小栈的所有操作（入栈、出栈和查找最小值）均在O(1)时间内完成，并且每个元素仅需存储一个额外的整数，确保空间效率。
最小栈适合用于哪些场景？
最小栈特别适用于竞争编程和实时系统，能够快速解决频繁的最小值查询。
➡️
