2-23 155.最小栈

Date：2022-02-27 17:45:52

题目：155.最小栈

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

分析

方法有：1.辅助栈法

思想为：需要两个栈，一个栈为正常栈，另一个栈为最小栈（辅助栈）。

• 正常栈中就进行正常 push、pop、top
• 最小栈的主要作用是满足 常数时间内检索最小元素 ，最小栈的栈顶永远是最小的元素，所以可以直接访问栈顶元素，即为最小元素

题解

// class不具有变量提升
class MinStack {
  private readonly stack = []
  private readonly minStack = []
  // assist stack
  // only for get min element

  private len = 0

  push(e: number) {
    this.stack.push(e)

    if (this.len == 0) {
      this.minStack.push(e)
    } else {
      const oldMin = this.minStack[this.len - 1] ?? Infinity
      this.minStack.push(Math.min(e, oldMin))
    }

    ++this.len
  }
  pop() {
    if (this.len == 0) return undefined

    const e = this.stack.pop()
    this.minStack.pop()

    --this.len

    return e
  }
  top() {
    return this.stack[this.len - 1]
  }
  getMin() {
    return this.minStack[this.len - 1]
  }
}

function main() {
  const stack = new MinStack()

  stack.push(-2)
  stack.push(0)
  stack.push(-3)

  console.log('[getMin]:', stack.getMin())
  console.log('[pop]:', stack.pop())
  console.log('[top]:', stack.top())
  console.log('[getMin]:', stack.getMin())
}

main()