Frontend Interview

Appearance

4. 实现最小栈 ​

来源：腾讯一面

题目 ​

实现一个栈，支持 push、pop、top、getMin 操作，其中 getMin 能在 O(1) 时间内获取栈中的最小元素。

代码 ​

js
// 实现栈push/pop/getMin等方法
// 腾讯一面

class Stack{
    constructor(){
        this.stack = [];
        this.minStack = [];
    }

    push(x){
        this.stack.push(x);
        if(this.minStack.length === 0 || x <= this.getMin()){
            this.minStack.push(x);
        }
    }

    pop(){
        const val = this.stack.pop();
        if(val === this.getMin()){
            this.minStack.pop();
        }
    }

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

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

const stack = new Stack();
stack.push(3);
stack.push(5);
stack.push(2);
console.log(stack.getMin()); // 2
stack.pop();
console.log(stack.getMin()); // 3
console.log(stack.top());    // 5

思路 ​

使用辅助栈同步记录最小值：

  1. 维护两个栈：
    • stack：正常的数据栈
    • minStack：最小值栈，栈顶始终是当前栈中的最小值
  2. push(x) 操作：
    • 将 x 压入 stack
    • 如果 x 小于等于当前最小值，也压入 minStack
  3. pop() 操作：
    • 弹出 stack 栈顶元素
    • 如果弹出的值等于当前最小值，也弹出 minStack 栈顶
  4. getMin() 操作：
    • 直接返回 minStack 栈顶元素

关键点 ​

  • 使用辅助栈同步维护最小值，空间换时间
  • push 时判断条件是 <=，不是 <，因为可能有重复的最小值
  • pop 时需要判断弹出的值是否是最小值，如果是则同步弹出 minStack
  • 所有操作的时间复杂度都是 O(1)
  • 空间复杂度 O(n)