最小栈

题目描述

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

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

测试用例

输入

[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出

[null,null,null,null,-3,null,0,-2]

解释

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); –> 返回 -3.
minStack.pop();
minStack.top(); –> 返回 0.
minStack.getMin(); –> 返回 -2.

解题思路

重点是如何在常数时间内获取到最小值.这个要求意味着我们每个节点,不能走仅存储当前值,还需要同步存储当前值入栈之后,栈内的最小值,这样直接读取栈顶元素,即可获取到站内最小值. 需要注意的是,相关操作之前记得判断栈是否为空

代码实现

// node 栈内每一个元素的结构
//
// Author : go_developer@163.com<白茶清欢>
//
// Date : 3:58 下午 2021/2/10
type node struct {
  current int // 当前值
  min     int // 最小值
}
type MinStack struct {
  stack []node
}

/** initialize your data structure here. */
func Constructor() MinStack {
  return MinStack{
    stack: make([]node, 0),
  }
}

func (this *MinStack) Push(x int) {
  newNode := node{
    current: x,
    min:     x,
  }
  if this.IsEmpty() {
    this.stack = append(this.stack, newNode)
  } else {
    if this.stack[len(this.stack)-1].min < x {
      newNode.min = this.stack[len(this.stack)-1].min
    }
    this.stack = append(this.stack, newNode)
  }
}

func (this *MinStack) Pop() {
  if this.IsEmpty() {
    return
  }
  this.stack = this.stack[:len(this.stack)-1]
}

func (this *MinStack) Top() int {
  if this.IsEmpty() {
    return 0
  }
  return this.stack[len(this.stack)-1].current
}

func (this *MinStack) GetMin() int {
  if this.IsEmpty() {
    return 0
  }
  return this.stack[len(this.stack)-1].min
}

func (this *MinStack) IsEmpty() bool {
  return len(this.stack) == 0
}