Min Stack Leetcode

#1

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.
```

#2

The below code creates an element type for `Stack` which can hold the `val` and also the latest `min` value. Instead of using two stacks, this code reduces the overall time complexity by 100%

``````type element struct{
val int
min int
}

type MinStack struct {
stack []element
}

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

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

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

func (this *MinStack) Top() int {
if len(this.stack)!=0{
return this.stack[len(this.stack)-1].val
}
return 0
}

func (this *MinStack) GetMin() int {
if len(this.stack)!=0{
return this.stack[len(this.stack)-1].min
}
return 0
}

/**
* 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();
*/
``````