Min Stack

1. Problem Description

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

2. Approach

1. Approach 1
   • Because a stack is last-in, first-out, use an additional minimum stack to store the minimum element corresponding to the current data stack

3. Implementation

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


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


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

}


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


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


func (this *MinStack) GetMin() int {
    if len(this.min) == 0{
        return 0
    }

    return this.min[len(this.min)-1]
}


/**
 * Your MinStack object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Push(val);
 * obj.Pop();
 * param_3 := obj.Top();
 * param_4 := obj.GetMin();
 */

4. References

• Min Stack - LeetCode