设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。 pop() -- 删除栈顶的元素。 top() -- 获取栈顶元素。 getMin() -- 检索栈中的最小元素。 MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.用O(n)的辅助空间，及用另一个栈记录min
type MinStack struct { d []int m []int } /** initialize your data structure here. */ func Constructor() MinStack { var d MinStack return d } func (this *MinStack) Push(x int) { this.d = append(this.d, x) if len(this.m) == 0 { this.m = append(this.m, x) } else { if x < this.m[len(this.m)-1] { this.m = append(this.m, x) } else { this.m = append(this.m, this.m[len(this.m)-1]) } } } func (this *MinStack) Pop() { this.d = this.d[:len(this.d)-1] this.m = this.m[:len(this.m)-1] } func (this *MinStack) Top() int { return this.d[len(this.d)-1] } func (this *MinStack) GetMin() int { return this.m[len(this.m)-1] } 栈中记录X-min差值，通过差值符号判断min的更替，额外空间O(1) /** brief: 额外的一个空间用于记录min值;栈中记录X-min的差值;X-min的符号变化表示min发生改变 min不变，则X-min>=0， min变，则X-min1<=0,此时将记录min2=X,X-min1; Top时，由min2-(X-min1)=min1,可得出上一阶段的min 同时,因为min更新，X=min2，即min2是刚变化的X值 */ type MinStack struct { d []int m int } /** initialize your data structure here. */ func Constructor() MinStack { var d MinStack return d } func (this *MinStack) Push(x int) { var tmp int = 0 if len(this.d) == 0 { this.m = x } tmp = x - this.m this.d = append(this.d, tmp) if tmp < 0 { this.m = x } } func (this *MinStack) Pop() { if len(this.d) == 0 { return } if this.d[len(this.d)-1] < 0 { this.m = this.m - this.d[len(this.d)-1] } this.d = this.d[:len(this.d)-1] } func (this *MinStack) Top() int { if len(this.d) == 0 { panic("empty stack") } if this.d[len(this.d)-1] < 0 { return this.m } else { return this.d[len(this.d)-1] + this.m } } func (this *MinStack) GetMin() int { return this.m }