写在前面
栈，是一个先进后出的数据结构。面试中经常会遇到栈的变体，比如最小栈，leetcode上原题：最小栈
题目描述
思路
拿到这个题，作者想法是用单链表维持一个递增队列，每层插入(push)或者删除(pop)的时候，往递增队列中插入或者删除对应的元素。获取栈内最小元素的时候直接返回递增队列的头节点就可以了。
这样虽然满足了在O(1)时间内检索到最小元素，但是插入、删除的时间复杂的就变成了O(n^2),题目对插入、删除没有做时间要求，就先这样实现，毕竟也没有想到更好的办法。（做完之后看题解发现了一种更好的办法，后文会介绍）
代码
定义数据结构
type Node struct {
Val int
next *Node
}
type MinStack struct {
stackData []int // 存放堆栈数据
head *Node // 递增链表
top int // 指向栈顶元素
}实现要求的几个方法
func Constructor() MinStack {
return MinStack{
stackData: make([]int, 0),
top: -1,
}
}
func (this *MinStack) Push(val int) {
if len(this.stackData) == this.top+1 {
// 说明stackData已满，需要扩容
this.stackData = append(this.stackData, val)
this.top++
} else {
this.top++
this.stackData[this.top] = val
}
// 放入队列
p := this.head
// 如果队列是空，则初始化队列
if p == nil {
this.head = &Node{Val: val}
return
}
// 如果当前值小于头节点的值，则放入第一个节点
if p.Val >= val {
tmp := &Node{Val: val}
tmp.next = this.head
this.head = tmp
return
}
for p.next != nil && p.next.Val < val {
p = p.next
}
// 放入p后面那个节点
tmp := &Node{Val: val}
tmp.next = p.next
p.next = tmp
}
func (this *MinStack) Pop() {
if this.top < 0 {
return
}
removeVal := this.stackData[this.top]
// 出栈
this.top--
// 从队列中移除removeVal
if this.head.Val == removeVal {
// 是队首元素
this.head = this.head.next
return
}
p := this.head
for p.next != nil && p.next.Val != removeVal {
p = p.next
}
// 移除p.next节点
p.next = p.next.next
}
func (this *MinStack) Top() int {
if this.top < 0 {
return 0
}
return this.stackData[this.top]
}
func (this *MinStack) GetMin() int {
if this.top < 0 {
return 0
}
return this.head.Val
}该算法虽然通过了，但不是最优的
题解
思路
要做出这道题目，首先要理解栈结构先进后出的性质。
对于栈来说，如果一个元素 a 在入栈时，栈里有其它的元素 b, c, d，那么无论这个栈在之后经历了什么操作，只要 a 在栈中，b, c, d 就一定在栈中，因为在 a 被弹出之前，b, c, d 不会被弹出。
因此，在操作过程中的任意一个时刻，只要栈顶的元素是 a，那么我们就可以确定栈里面现在的元素一定是 a, b, c, d。
那么，我们可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 a，我们就可以直接返回存储的最小值 m。
算法
按照上面的思路，我们只需要设计一个数据结构，使得每个元素 a 与其相应的最小值 m 时刻保持一一对应。因此我们可以使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。
当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；
当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；
在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。
代码
type MinStack struct {
stackData []int // 存放堆栈数据
minStackData []int // 辅助栈
top int // 指向栈顶元素
}
func Constructor() MinStack {
return MinStack{
stackData: make([]int, 0),
minStackData: make([]int, 0),
top:-1,
}
}
func (this *MinStack) Push(val int) {
if len(this.stackData) == this.top+1 {
// 说明stackData已满，需要扩容
this.stackData = append(this.stackData, val)
if this.top==-1 || this.minStackData[this.top] > val {
this.minStackData = append(this.minStackData, val)
} else {
this.minStackData = append(this.minStackData, this.minStackData[this.top])
}
this.top++
} else {
this.top++
if this.top==0 || this.minStackData[this.top-1] > val {
this.minStackData[this.top] = val
} else {
this.minStackData[this.top] = this.minStackData[this.top-1]
}
this.stackData[this.top] = val
}
}
func (this *MinStack) Pop() {
if this.top < 0 {
return
}
this.top--
}
func (this *MinStack) Top() int {
if this.top < 0 {
return 0
}
return this.stackData[this.top]
}
func (this *MinStack) GetMin() int {
if this.top < 0 {
return 0
}
return this.minStackData[this.top]
}题解中提到的算法确实不错，插入、删除的时间复杂的都是O(1)
