155. 最小栈 🟨

题目

leetcode 中等

题目

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

实现 MinStack 类:

MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int 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.

题解

两个栈

时间复杂度：O(1)

所有的 push、pop、top、getMin 操作都没有任何循环遍历，仅仅是数组末尾的操作，绝对的常数时间复杂度。
空间复杂度：O(N)

我们额外使用了一个 min_stack 数组，最坏情况下保存与数据栈相同数量的元素。这就是典型的“空间换时间”。

class MinStack {
  constructor() {
    this.stack = []
    // ‼️ 初始化时放入一个无穷大，可以避免第一次比较时栈为空的判断边界
    this.min_stack = [Infinity]
  }

  push(val) {
    this.stack.push(val)
    const currentMin = Math.min(val, this.min_stack[this.min_stack.length - 1])
    this.min_stack.push(currentMin)
  }

  pop() {
    this.stack.pop()
    this.min_stack.pop()
  }

  top() {
    return this.stack[this.stack.length - 1]
  }

  getMin() {
    return this.min_stack[this.min_stack.length - 1]
  }
}

const minStack = new MinStack()
minStack.push(-2)
minStack.push(0)
minStack.push(-3)
console.log(minStack.getMin())
minStack.pop()
console.log(minStack.top())
console.log(minStack.getMin())

执行结果

-3
0
-2

一个栈存obj

class MinStack {
  constructor() {
    this.stack = []
  }

  push(val) {
    if (this.stack.length === 0) {
      // 第一个进来的，它自己就是最小值
      this.stack.push({ val: val, min: val })
    } else {
      // 后续进来的，和前一个状态的最小值去比较
      const currentMin = Math.min(val, this.stack[this.stack.length - 1].min)
      this.stack.push({ val: val, min: currentMin })
    }
  }

  pop() {
    this.stack.pop()
  }

  top() {
    return this.stack[this.stack.length - 1].val
  }

  getMin() {
    return this.stack[this.stack.length - 1].min
  }
}

const minStack = new MinStack()
minStack.push(-2)
minStack.push(0)
minStack.push(-3)
console.log(minStack.getMin())
minStack.pop()
console.log(minStack.top())
console.log(minStack.getMin())

执行结果

-3
0
-2

本页目录

题目

题解

一个栈存obj