LeetCode(5) 最小栈

xbdyhh · 2020-11-01 22:32:39 · 353 次点击 · 预计阅读时间 1 分钟 · 大约8小时之前 开始浏览    
这是一个创建于 2020-11-01 22:32:39 的文章,其中的信息可能已经有所发展或是发生改变。

题目:

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

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

思路:

栈相关的进栈、出栈的操作不在赘述,这道题目的主要问题出在了在常数时间内查询栈内最小数,这里采用辅助栈的方式,每次压栈是,除了把需要压入的数压入储存栈的同时,将当前最小数比较后压入最小栈。出栈时也同时删除两栈的栈顶元素。一下为代码实现。

type MinStack struct {
stack []int
minStack []int
}
func Constructor() MinStack {
   return MinStack{
      stack: []int{},
 minStack: []int{},
 }
}
func (this *MinStack) Push(x int)  {
   this.stack = append(this.stack,x)
   if len(this.minStack) != 0{
      minNum := min(x,this.minStack[len(this.minStack)-1])
      this.minStack = append(this.minStack,minNum)
   }else{
      this.minStack = append(this.minStack,x)
   }
   return
}
func (this *MinStack) Pop()(x int){
   x = this.stack[len(this.stack)-1]
   this.minStack = append(this.minStack[:len(this.minStack)-1])
   this.stack = append(this.stack[:len(this.stack)-1])
   return
}
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
}

image.png


有疑问加站长微信联系(非本文作者)

本文来自:Segmentfault

感谢作者:xbdyhh

查看原文:LeetCode(5) 最小栈

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

353 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传