中文
devexamples

Stack With O(1) Minimum

Track the minimum of a numeric stack in constant time using a parallel minimum stack, without scanning elements.

JavascriptData Integrity

Code

snippet
export class MinStack {
  #values = [];
  #minimums = [];

  push(value) {
    if (typeof value !== "number" || Number.isNaN(value)) {
      throw new TypeError("value must be a number");
    }
    this.#values.push(value);
    const currentMin = this.#minimums.length > 0
      ? this.#minimums[this.#minimums.length - 1]
      : Infinity;
    this.#minimums.push(Math.min(value, currentMin));
    return this;
  }

  pop() {
    if (this.#values.length === 0) return undefined;
    this.#minimums.pop();
    return this.#values.pop();
  }

  peek() {
    return this.#values[this.#values.length - 1];
  }

  min() {
    return this.#minimums[this.#minimums.length - 1];
  }

  get size() {
    return this.#values.length;
  }

  toArray() {
    return [...this.#values];
  }
}

Related Examples