最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

type MinStack struct {
    Val        []int
    Min        int
}


/** initialize your data structure here. */
func Constructor() MinStack {
    return MinStack{Val: []int{}, Min: 0}
}


func (this *MinStack) Push(x int)  {
    if x < this.GetMin() || len(this.Val) == 0 {
        this.Min = x
    }
    this.Val = append(this.Val, x)
}


func (this *MinStack) Pop()  {
    top := this.Top()
    this.Val = this.Val[:len(this.Val)-1]
    if top > this.Min {
        return
    }
    this.Min = this.Top()
    for _, v := range this.Val {
        if v < this.Min {
            this.Min = v
        }
    } 
}


func (this *MinStack) Top() int {
    if len(this.Val) > 0 {
        return this.Val[len(this.Val)-1]
    }
    return 0
}


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


/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(x);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.GetMin();
 */

维护一个最小值变量，min，push和pop的时候更新min，获取直接返回，但是pop的复杂度不为O(1)了

优化： 空间换时间，每个元素都维护一个最小值

type MinStack struct {
    s []Node
}
type Node struct {
	d int //data
	m int //current min
}

// 维护两个结构体，一个栈，一个值，每个值都加上当前最小值这个元素


/** initialize your data structure here. */
func Constructor() MinStack {
   return MinStack{}
}


func (this *MinStack) Push(x int)  {
	// 设置最小值
	d := Node{d:x,m:x}
	// 如果当前栈里有值了，则进行最小值比较，更新最小值
	// 也就是说新加入的元素，栈顶元素保存的最小值就是当前最小的
	if len(this.s)>0 &&this.s[len(this.s)-1].m< x{
		d.m=this.s[len(this.s)-1].m
	}
     this.s = append(this.s,d)

}


func (this *MinStack) Pop()  {
	this.s = this.s[:len(this.s)-1]
}


func (this *MinStack) Top() int {
	return this.s[len(this.s)-1].d
}


func (this *MinStack) GetMin() int {
	// 获取最小值只需要返回栈顶保存的最小值
	return this.s[len(this.s)-1].m
}