面试题 03.02. 栈的最小值
请设计一个栈，除了常规栈支持的pop与push函数以外，还支持min函数，该函数返回栈元素中的最小值。执行push、pop和min操作的时间复杂度必须为O(1)。
示例：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
原站题解
golang 解法, 执行用时: 12 ms, 内存消耗: 8.3 MB, 提交时间: 2021-06-10 23:23:42
type MinStack struct {
q []int
sq []int
}
/** initialize your data structure here. */
func Constructor() MinStack {
return MinStack{
q: []int{},
sq: []int{math.MaxInt32},
}
}
func (this *MinStack) Push(x int) {
this.q = append(this.q, x)
top := this.sq[len(this.sq)-1]
this.sq = append(this.sq, min(x, top))
}
func (this *MinStack) Pop() {
this.q = this.q[:len(this.q)-1]
this.sq = this.sq[:len(this.sq)-1]
}
func (this *MinStack) Top() int {
return this.q[len(this.q)-1]
}
func (this *MinStack) GetMin() int {
return this.sq[len(this.sq)-1]
}
func min(x, y int) int {
if x > y {
return y
}
return x
}
/**
* 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();
*/