LeetCode(5) 最小栈

xbdyhh · · 340 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

题目：

设计一个支持 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
}