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