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

定义带min函数的栈数据结构：

• 实现一个能够得到栈中最小元素的min函数；
• 调用min、push及pop的时间复杂度为O(1)；

题解分析

普通栈的push()和pop()函数的复杂度为O(1)，但获取栈最小值min()函数需要遍历整个栈，复杂度为O(N)；要将min()函数复杂度降为O(1)，需要借助辅助栈：

• 数据栈All：存储所有元素，实现入栈push()函数、出栈pop()函数、获取栈顶top()函数的正常逻辑；
• 辅助栈Ordered：存储所有非严格降序元素的子序列（栈All中的最小元素始终对应栈B的栈顶元素。

函数实现：

• push：把元素压入All中，若元素不大于Ordered.top()中的元素，则也压入Ordered栈中；
• pop：从All中弹出元素，若Ordered.top()等于弹出元素，则也从Ordered中弹出元素；
• top：获取All的top元素即可；
• min：获取Ordered的top元素；

复杂度：

• 时间：所有操作都为O(1)；
• 空间：最多All与Ordered中包含全部元素，所以为O(N)；

代码实现

golang中没有默认的stack库，使用切片模拟（只在尾部插入与删除）：

• 插入时用append；
• 删除时通过切片操作实现；

栈结构定义：

type MinStack struct {
   	All [] int	Ordered [] int}

在使用栈前，需要先通过Constructor构造出栈：

func Constructor() MinStack {
   	return MinStack{
   		All: make([]int, 0),		Ordered: make([]int, 0),	}}func (this *MinStack) Push(x int)  {
   	this.All = append(this.All, x)	if len(this.Ordered)==0 || this.Ordered[len(this.Ordered)-1]>=x{
   		this.Ordered = append(this.Ordered, x)	}}func (this *MinStack) Pop()  {
   	if len(this.All)==0{
   		return	}	result := this.All[len(this.All)-1]	this.All = this.All[:len(this.All)-1]	if result == this.Ordered[len(this.Ordered)-1]{
   		this.Ordered = this.Ordered[:len(this.Ordered)-1]	}}func (this *MinStack) Top() int {
   	if len(this.All)==0{
   		return 0	}	return this.All[len(this.All)-1]}func (this *MinStack) Min() int {
   	if len(this.Ordered)==0{
   		return 0	}	return this.Ordered[len(this.Ordered)-1]}func TestStack()  {
   	mStack := Constructor()	mStack.Push(-2)	mStack.Push(0)	mStack.Push(-3)	fmt.Println(mStack.Min())	mStack.Pop()	fmt.Println(mStack.Top())	fmt.Println(mStack.Min())}

转载地址：http://hwilf.baihongyu.com/