41 - 最小栈

题目

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

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

示例:

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

解答

存一个最小值

作者：lovesora
链接：https://leetcode-cn.com/problems/two-sum/solution/jsjie-fa-by-lovesora-17/

/**
 * initialize your data structure here.
 */
var MinStack = function () {
  this.stack = []
  this.min = null
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function (x) {
  this.stack.push(x)
  if (this.min > x || this.min === null) {
    this.min = x
  }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
  const pop = this.stack.pop()
  if (pop === this.min) {
    this.min = Math.min(...this.stack)
  }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function () {
  return this.stack[this.stack.length - 1]
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function () {
  return this.min
};

Runtime: 96 ms, faster than 93.84% of JavaScript online submissions for Min Stack.
Memory Usage: 44.5 MB, less than 45.71% of JavaScript online submissions for Min Stack.

第15行被坑了一下，因为一般遇到需要判断null都会习惯性写成：!this.min。

if (this.min > x || !this.min) {
  this.min = x
}

但是0就是false，也就是说只要min是0，不管再输入什么值，都会改写掉最小值。如果最小值是0，就永远无法存到。

因此只能写成this.min === null。可以说这是偷懒的下场。。

26行的做法参考[这个解答](https://leetcode.com/problems/min-stack/discuss/127173/JS-solution-(beats-100))，之前的做法是用`reduce`，遍历整个数组，两两比对留下最小值

this.min = this.stack.length ? this.stack.reduce((min, cur) => Math.min(min, cur), Number.MAX_SAFE_INTEGER) : null

感觉明显复杂了很多。

还有用for循环遍历就更不用提了。

不过那个解答return pop了，而其实不用，因为pop函数return的是{void}，也就是说无需return

34行对top的处理，这是我看到最好的。。

之前的想法，是先pop出顶上的值，再push回去，明显绕了一大圈。

为了避免判断0的情况，想到了先用最大值赋值min的做法：

var MinStack = function () {
  this.stack = []
  this.min = Number.MAX_SAFE_INTEGER   // 赋值
};

MinStack.prototype.push = function (x) {
  this.stack.push(x)
  this.min = x < this.min ? x : this.min   // 没有null的情况可以直接判断
};

// 剩下的都一样
...

Runtime: 108 ms, faster than 62.53% of JavaScript online submissions for Min Stack.
Memory Usage: 44.7 MB, less than 27.62% of JavaScript online submissions for Min Stack.

感觉比之前要慢了不少。看来每次判断null比用最大值，更划算一些。

go

go似乎没发用存一个最小值实现。

首先min没法定义为null，因为是int类型的，默认零值就是0了。但如果定义为0，那么万一来的数全比0大呢？如果专门对零做判断，万一来的最小值是0呢？
min也没法定义为最大安全数，因为最大安全数分int32和int64，但就是没有int的最大数。
其次go没有类似于js的math.Min，只能比较float64，而且只能是两两比较。
只能想到一个比较原始的做法来取最小值：

...
for _, elem := range this.stack {
  if elem < this.min {
    this.min = elem
  }
  runtime.Gosched()
}
...

看到题解，普遍采用的是多存一个辅助栈的做法：

即，新开一个数组min，如果新push进来的数小于等于min的最小数，就push进min；出栈的时候，如果辅助栈顶和原来额数组一样，那么也要出栈一个，不然就不出栈。

作者：elliotxx 链接：https://leetcode-cn.com/problems/two-sum/solution/32msgo-shi-xian-by-elliotxx/

type MinStack struct {
    data []int
    min  []int
}

/** initialize your data structure here. */
func Constructor() MinStack {
    var stack MinStack
    return stack
}

func (this *MinStack) Push(x int) {
    this.data = append(this.data, x)
    if len(this.min) == 0 || this.min[len(this.min)-1] >= x {  // 判断为0感觉是为了防止初值时的panic
        this.min = append(this.min, x)
    }
}

func (this *MinStack) Pop() {
    if this.min[len(this.min)-1] == this.data[len(this.data)-1] {
        this.min = this.min[0 : len(this.min)-1]
    }
    this.data = this.data[0 : len(this.data)-1]
}

func (this *MinStack) Top() int {
  if len(this.data) == 0 {                        // 防止一上来先Top()，导致panic
        return 0
    }
    return this.data[len(this.data)-1]
}

func (this *MinStack) GetMin() int {
    if len(this.min) == 0 {                            // 防止一上来先getmin()，导致panic
        return 0
    }
    return this.min[len(this.min)-1]
}

Runtime: 12 ms, faster than 100.00% of Go online submissions for Min Stack.
Memory Usage: 8.2 MB, less than 54.55% of Go online submissions forMin Stack.

看到了一个用链表的做法

感觉会更优一点，毕竟需要读取的只是最小值。

https://leetcode.com/problems/min-stack/discuss/205471/beat-100-in-Go

// ======= chain ========
type Node struct {
    data int
    next *Node
}

type Stack struct {
    head *Node
}

func NewStack() *Stack {
    return &Stack{
        head: &Node{},
    }
}

func (s *Stack) push(v int) {
    n := &Node{
        data: v,
        next: nil,
    }
    n.next = s.head.next
    s.head.next = n
}

func (s *Stack) pop() {
    s.head.next = s.head.next.next
}

func (s *Stack) isEmpty() bool {
    return s.head.next == nil
}

func (s *Stack) top() int {
    if s.head.next != nil {
        return s.head.next.data
    }
    return 0
}

type MinStack struct {
    data []int
    min  *Stack
}

// ==== 上面都是链表的定义，下面开始答题 ====

/** initialize your data structure here. */
func Constructor() MinStack {
    return MinStack{
        data: []int{},
        min:  NewStack(),
    }
}

func (this *MinStack) Push(x int) {
    this.data = append(this.data, x)
    if this.min.isEmpty() || this.min.top() >= x {
        this.min.push(x)
    }
}

func (this *MinStack) Pop() {
    if this.min.top() == this.data[len(this.data)-1] {
        this.min.pop()
    }
    this.data = this.data[0 : len(this.data)-1]
}

func (this *MinStack) Top() int {
    if len(this.data) == 0 {
        return 0
    }
    return this.data[len(this.data)-1]
}

func (this *MinStack) GetMin() int {
    return this.min.top()
}

Runtime: 20 ms, faster than 75.68% of Go online submissions for Min Stack.
Memory Usage: 8.5 MB, less than 14.29% of Go online submissions forMin Stack.

好像反而慢了很多。。。可能是因为链表的操作更加麻烦吧

Previous75 - 二叉树的所有路径 Next27 - 最小差值

Last updated 5 years ago

Was this helpful?