Go语言栈的最小值实现（小白也能懂的数据结构实战教程）

问题：如何快速获取栈的最小值？

普通栈只支持 push（入栈）、pop（出栈）和 top（查看栈顶）操作。如果我们每次都要遍历整个栈来找最小值，时间复杂度是 O(n)，效率很低。

我们的目标是设计一个特殊的栈，支持以下操作：

• Push(x)：将元素 x 压入栈
• Pop()：弹出栈顶元素
• Top()：获取栈顶元素
• GetMin()：获取栈中最小元素（O(1) 时间复杂度）

解决方案：双栈法

我们可以使用两个栈：

• 主栈（mainStack）：存储所有元素
• 辅助栈（minStack）：存储当前栈中的最小值

每当有新元素入栈时，我们同时更新 minStack：如果新元素小于等于 minStack 的栈顶，则将其也压入 minStack。这样，minStack 的栈顶始终是当前全局最小值。

Go 语言完整实现

下面是一个完整的、可运行的 Go 代码示例：

package mainimport "fmt"// MinStack 支持获取最小值的栈type MinStack struct {    mainStack []int  // 主栈    minStack  []int  // 辅助栈，存储最小值}// Constructor 初始化栈func Constructor() MinStack {    return MinStack{        mainStack: make([]int, 0),        minStack:  make([]int, 0),    }}// Push 将元素压入栈func (ms *MinStack) Push(val int) {    ms.mainStack = append(ms.mainStack, val)        // 如果 minStack 为空，或者 val 小于等于当前最小值，则压入 minStack    if len(ms.minStack) == 0 || val <= ms.minStack[len(ms.minStack)-1] {        ms.minStack = append(ms.minStack, val)    }}// Pop 弹出栈顶元素func (ms *MinStack) Pop() {    if len(ms.mainStack) == 0 {        return    }        top := ms.mainStack[len(ms.mainStack)-1]    ms.mainStack = ms.mainStack[:len(ms.mainStack)-1]        // 如果弹出的元素等于当前最小值，则 minStack 也要弹出    if top == ms.minStack[len(ms.minStack)-1] {        ms.minStack = ms.minStack[:len(ms.minStack)-1]    }}// Top 获取栈顶元素func (ms *MinStack) Top() int {    if len(ms.mainStack) == 0 {        panic("stack is empty")    }    return ms.mainStack[len(ms.mainStack)-1]}// GetMin 获取栈中最小元素func (ms *MinStack) GetMin() int {    if len(ms.minStack) == 0 {        panic("stack is empty")    }    return ms.minStack[len(ms.minStack)-1]}// 示例使用func main() {    obj := Constructor()    obj.Push(-2)    obj.Push(0)    obj.Push(-3)        fmt.Println("当前最小值:", obj.GetMin()) // 输出: -3        obj.Pop()    fmt.Println("栈顶元素:", obj.Top())      // 输出: 0    fmt.Println("当前最小值:", obj.GetMin()) // 输出: -2}

代码解析

- Push：除了压入主栈，还会判断是否需要更新 minStack。

- Pop：弹出主栈元素后，如果该元素等于当前最小值，minStack 也要同步弹出。

- GetMin：直接返回 minStack 的栈顶，时间复杂度为 O(1)。

为什么这个方法有效？

因为 minStack 始终维护着“历史最小值序列”。即使主栈弹出了某些元素，只要最小值还在栈中，minStack 就保留它；一旦最小值被弹出，minStack 也同步更新，确保栈顶始终是当前有效的最小值。

总结

通过双栈法，我们成功实现了支持 O(1) 获取最小值的栈。这不仅加深了你对 Go语言栈实现 的理解，也展示了如何用空间换时间优化算法。希望这篇 数据结构教程 能帮助你在 Go编程入门 之路上更进一步！

小提示：你可以将上述代码复制到 Go Playground 或本地 IDE 中运行，观察输出结果，加深理解。