你的浏览器还没开启 Javascript 功能!

算法题 查找最小数栈

题目

设计一个class,来实现栈:
除了 poppush 等栈的常规操作,还需要添加一个 min 函数,返回栈的最小元素
要求:函数 min、push 以及 pop 的时间复杂度都是O(1)

分析

  • 常规 pop push
  • min,返回栈最小元素
  • 要求三个方法时间复杂度为O(1)

实现

先实现常规 pop、push 方法,栈的数据用数组保存。
先来简单实现一下:


class MyStack {
    private arr: number[] = [];

    public pop(): number {
        return this.arr.pop();
    }
    public push(n: number) {
        this.arr.push(n);
    }
}

这时候还需要补全一个方法,min,返回已存入数据中最小数。
那也很OK啊,直接用一个变量来存入呗。然后push的时候判断一下。


class MyStack {
    private arr: number[] = [];
    private minNumber: number;

    public pop(): number {
        return this.arr.pop();
    }
    public push(n: number) {
        this.arr.push(n);
        // 这里做最小值判断更新
        if(this.minNumber === void 0 || n < this.minNumber) {
            this.minNumber = n;
        }
    }
    // 获取最小值
    public min(): number {
        return this.minNumber;
    }
}

要素察觉

然而,事情没有这么简单~
这样的min方法会出现问题,如果栈最小的数被pop出去了,这下minNumber无法感知到倒数第二小的数做更新。

从而,我们需要维护另一个最小数的栈来实现,并且满足O(1)的时间复杂度。


class MyStack {
    // 数据栈
    private arr: number[] = [];
    // 最小数栈
    private minArr: number[] = [];

    public pop(): number {
        const pop = this.arr.pop();
        // 数据为空则返回
        if(pop === void 0) {
            return;
        }
        // 判断出栈的数据是否为最小数
        if(pop === this.min()) {
            // 最小数也出栈
            this.minArr.pop();
        }
        return pop;
    }
    public push(n: number) {
        this.arr.push(n);
        // 这里做最小值判断更新
        const minNumber = this.min();
        // 最小数栈为空 或者 小于最小数
        if(minNumber === void 0 || n < minNumber) {
            this.minArr.push(n);
        }
    }
    // 获取最小值
    public min(): number {
        return this.minArr[this.minArr.length - 1];
    }
}