155. Min Stack

题目

设计一个栈，支持 push，pop，和 top。并且能够在常量时间内检索最小元素。

解析

栈，先进后出。
设计一个指针指向最小元素。因为空间无限大，采用链表实现。
这里有一个问题，一旦 pop 弹出了最小值，需要修改最小值的指向。如何在常量时间内找到最小值呢。
维护一个最小值列表，插入的时候，如果更新了最小值，就把这个最小值压入最小值栈，弹出的时候，如果弹出了最小值，同时将最小值弹栈。

为了判断 node 相等，最好是用指针判断，为此，需要在 node 里内置两个指针，一个用来构建最小栈，一个用来构建普通栈。
老规矩，两个栈都用一个虚拟头指针避免边界检查。

伪代码

push

//  插入普通栈
node = &Node{}
node.next = head.next
head.next = node

// 如果值小于等于当前最小值，插入最小栈
if node.value <= min.next.val 
  node.minnext = min.minnext
  min.minnext = node

pop

node := head.next
// 普通栈弹出 node
head.next = head.next.next

// 如果 node 是当前最小值，最小栈弹出 node
if min.minnext = node
  min.minnext = min.minnext.minnext

代码

type Node struct {
    Value int
    Next *Node
    NextMin *Node
}

type MinStack struct {
    Head *Node
    Min *Node
}

func Constructor() MinStack {
    return MinStack{
        Head: &Node{},
        Min:&Node{},
    }
}

func (this *MinStack) Push(val int)  {
    node := &Node{Value:val, Next:this.Head.Next}
    this.Head.Next = node
    
    if this.Min.NextMin == nil || val <= this.Min.NextMin.Value {
        node.NextMin = this.Min.NextMin
        this.Min.NextMin = node
    }
}

func (this *MinStack) Pop()  {
    if this.Head.Next == nil {
        return
    }
    node := this.Head.Next
    this.Head.Next = this.Head.Next.Next
    if node != nil && this.Min.NextMin == node {
        this.Min.NextMin = this.Min.NextMin.NextMin
    }
}


func (this *MinStack) Top() int {
    return this.Head.Next.Value
}


func (this *MinStack) GetMin() int {
    return this.Min.NextMin.Value
}

image.png