Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) -- Push element x onto stack.
  • pop() -- Removes the element on top of the stack.
  • top() -- Get the top element.
  • getMin() -- Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

Solution:

type MinStack struct {
  data []int
  min []int
}


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


func (this *MinStack) Push(x int)  {
  if len(this.min)==0|| x<=this.min[len(this.min)-1]{
    this.min=append(this.min,x)
  }
  this.data=append(this.data,x)
}


func (this *MinStack) Pop()  {
  lenD:=len(this.data)
  if this.data[lenD-1]==this.GetMin(){
    this.min=this.min[:len(this.min)-1]
  }
  this.data=this.data[:lenD-1]
}


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


func (this *MinStack) GetMin() int {
  lenD:=len(this.min)
  if lenD>0{
  return this.min[lenD-1]
  }else{
    return this.data[len(this.data)-1]
  }
}