设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
❝
❞
题目中提到了栈,我们首先要想到栈结构先进后出的性质。
对于栈来说,如果一个元素 a 在入栈时,栈里有其它的元素 b, c, d,那么无论这个栈在之后经历了什么操作,只要 a 在栈中,b, c, d 就一定在栈中,因为在 a 被弹出之前,b, c, d 不会被弹出。
题目要求「常数时间内」检索到最小元素,那么通过遍历来查找最小元素这种方法就不可行了。我们可以采用空间换时间的方法,将每个元素入栈时把当前栈的最小值值存储起来。在这之后无论何时,如果栈顶元素是 a,我们就可以直接返回存储的最小值。
也就是我们需要维护两个栈,一个是元素栈,一个是元素栈内每个元素所对应的最小值栈。如下图,每个元素入栈的时候,把与之相对应的最小元素存入另一个栈。
type MinStack struct {
stack []int
minStack []int
}
/** initialize your data structure here. */
func Constructor() MinStack {
return MinStack{
stack: []int{},
minStack: []int{math.MaxInt64},
}
}
func (this *MinStack) Push(val int) {
this.stack = append(this.stack, val)
top := this.minStack[len(this.minStack)-1]
this.minStack = append(this.minStack, min(val, top))
}
func (this *MinStack) Pop() {
this.stack = this.stack[:len(this.stack)-1]
this.minStack = this.minStack[:len(this.minStack)-1]
}
func (this *MinStack) Top() int {
return this.stack[len(this.stack)-1]
}
func (this *MinStack) GetMin() int {
return this.minStack[len(this.minStack)-1]
}
func min(x, y int) int {
if x < y {
return x
}
return y
}
/**
* 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();
*/