最小栈

力扣 155. 最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

方案一：双栈结构，一个保存最小值，一个正常栈。

type MinStack struct {
    stack []int // 正常保存栈元素
    min   []int // 保存和 stack 下标对应的元素进入时的最小值
}


func Constructor() MinStack {
    return MinStack{
        // 初始化并加入哨兵值，两者都加入是为了让两者下标对应
        // 可以减少在 push 时对 min 数组的判断（否则要判断 min 是否为空）
        stack: []int{math.MaxInt32}, 
        min:   [] int{math.MaxInt32},
    }
}


func (this *MinStack) Push(val int)  {
    // 正常入栈
    this.stack = append(this.stack, val)
    // 和栈顶元素对比得出最小值后入栈
    this.min = append(this.min, min(this.min[len(this.min) - 1], val))
}


func (this *MinStack) Pop()  {
    // 两者都做出栈操作
    this.stack = this.stack[:len(this.stack) - 1]
    this.min = this.min[:len(this.min) - 1]
}


func (this *MinStack) Top() int {
    // 取栈顶
    return this.stack[len(this.stack) - 1]
}


func (this *MinStack) GetMin() int {
    // 取最小栈栈顶
    return this.min[len(this.min) - 1]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

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

力扣 155. 最小栈

CATALOG

FEATURED TAGS