LeetCode，Go 实现最小栈
力扣题目：
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
- push(x) —— 将元素 x 推入栈中。
- pop() —— 删除栈顶的元素。
- top() —— 获取栈顶元素。
- getMin() —— 检索栈中的最小元素。
❝
- 来源：力扣（LeetCode）
- 链接：https://leetcode-cn.com/problems/min-stack
❞
解题思路
题目中提到了栈，我们首先要想到栈结构先进后出的性质。
对于栈来说，如果一个元素 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();
*/
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-08-02，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
