题目描述
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) – 将元素 x 推入栈中。
pop() – 删除栈顶的元素。
top() – 获取栈顶元素。
getMin() – 检索栈中的最小元素。
链接：https://leetcode-cn.com/problems/min-stack
解题思路
这里使用了两个栈实现
- 一个栈实现主要的栈功能包括Push,Top,Pop等
第二个栈作为辅助栈，栈顶元素用来保存入栈数据的最小元素
1. 当push的是空栈时将该元素直接压入辅助栈 2. 当push的是非空栈时，判断入栈元素与辅助栈栈顶元素大小，如果比栈顶元素小则压栈，否则舍弃 3. 当pop时，出栈元素与辅助栈栈顶元素是否相等，如果相等则辅助栈同样执行出栈操作 4. 当getMin时直接返回辅助栈栈顶元素即可- 我在实现的时候主栈使用了切片数组+游标的方式，而辅助栈则使用了List这种结构。使用两种方式主要目的是为了更加熟悉go语言的特性。
Code
package main
import (
"container/list"
"fmt"
)
type MinStack struct {
len int //栈长度
use int //已使用
data [] int //主栈
stack *list.List //辅助栈，栈顶存放最小元素
}
/** initialize your data structure here. */
func Constructor() MinStack {
stack := MinStack{
len: 10,
use: 0,
data: make([] int, 10),
stack: list.New(),
}
return stack
}
func (this *MinStack) Push(x int) {
if this.use >= this.len {
return
}
this.data[this.use] = x
this.use++
if this.stack.Len() == 0 {
this.stack.PushBack(x)
} else if value, ok := this.stack.Back().Value.(int); ok{
if value >= x {
this.stack.PushBack(x)
}
}
}
func (this *MinStack) Pop() {
if this.use <= 0 {
return
}
if value, ok := this.stack.Back().Value.(int); ok {
if value == this.Top() {
e := this.stack.Back()
this.stack.Remove(e)
}
}
this.data[this.use-1] = 0
this.use--
}
func (this *MinStack) Top() int {
if this.use <= 0 {
if this.use > this.len {
return 0
}
}
return this.data[this.use-1]
}
func (this *MinStack) GetMin() int {
if value, ok := this.stack.Back().Value.(int); ok {
return value
}
return 0
}
func main() {
ms := Constructor()
ms.Push(2147483646)
ms.Push(2147483646)
ms.Push(2147483647)
ms.Top()
ms.Pop()
fmt.Println(ms.GetMin())
ms.Pop()
fmt.Println(ms.GetMin())
ms.Pop()
ms.Push(2147483647)
ms.Top()
fmt.Println(ms.GetMin())
ms.Push(-2147483648)
ms.Top()
fmt.Println(ms.GetMin())
ms.Pop()
fmt.Println(ms.GetMin())
fmt.Println(1111)
}
文档信息
- 本文作者：KcJia
- 本文链接：https://blog.kcjia.cn/2020/04/24/leetcode-155/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）