155.最小栈 👌

算法
按照上面的思路，我们只需要设计一个数据结构，使得每个元素 a 与其相应的最小值 m 时刻保持一一对应。因此我们可以使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。

• 当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；
• 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；
• 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。 ```go //辅助栈写法 type MinStack struct { stack []int minStack []int }

func Constructor() MinStack { return MinStack{ stack: []int{}, minStack: []int{math.MaxInt64}, } }

func (this *MinStack) Push(x int) { this.stack = append(this.stack, x) top := this.minStack[len(this.minStack)-1] this.minStack = append(this.minStack, min(x, top)) }

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

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

func (this *MinStack) GetMin() int { return this.minStack[len(this.minStack)-1] }

func min(x, y int) int { if x < y { return x } return y }

<a name="Vmgkq"></a>
### 解题思路
用两个stack很好解这一道题，需要额外 O(N) 的空间，这里提供一种 O(1) 额外空间的思路。<br />与其直接在 stack 存每个值，我们存每个值与当前最小值 min 的差值 （val-min）：
1. push：<br />1). 如果当前没有任何元素，则把 min 设为当前 val<br />2). 同时，往 stack 放 val-min
1. pop：<br />1). 如果栈顶元素是非负数（比之前的 min 大，或相同），则直接pop栈顶元素<br />2). 如果栈顶元素是负数（比之前的 min 小），则当前栈顶元素就是目前的 min， pop出来之后需要更新 min = min - （栈顶数值）
1. top：<br />1). 如果栈顶元素是正数（比之前的 min 大），则 top 数值 = min + （栈顶数值）<br />2). 如果栈顶元素是非正数（比之前的 min 小，或相同），则当前 top 元素就等于目前的 min
1. getMin：<br />直接 return min 即可
```go
//模拟写法
type MinStack struct {
    stk  []int
    min  int
    size int
}
/** initialize your data structure here. */
func Constructor() MinStack {
    return MinStack{stk: make([]int, 0), min: math.MaxInt64}
}
func (this *MinStack) Push(val int) {
    if this.size == 0 {
        this.min = val
    }
    this.stk = append(this.stk, val-this.min)
    if this.min > val {
        this.min = val
    }
    this.size++
}
func (this *MinStack) Pop()  {
    if this.stk[this.size-1] < 0 {
        this.min -= this.stk[this.size-1]
    }
    this.stk = this.stk[:this.size-1]
    this.size--
}
func (this *MinStack) Top() int {
    if this.stk[this.size-1] >= 0 {
        return this.min + this.stk[this.size-1]
    }
    return this.min
}
func (this *MinStack) GetMin() int {
    return this.min
}