155.最小栈

链接：155.最小栈
难度：Medium
标签：栈、设计
简介：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

题解 1 - javascript

• 编辑时间：2020-05-12
• 执行用时：156ms
• 内存消耗：45.6MB
• 编程语言：javascript
• 解法介绍：优化检索为 O1。

/**
 * initialize your data structure here.
 */
class MinStack {
  _arr = [];
  _min = [];
  /**
   * @param {number} x
   * @return {void}
   */
  push(x) {
    this._arr.push(x);
    const arrLen = this._arr.length - 1;
    if (this._min.length === 0) this._min.push(0);
    else {
      for (let i = 0, len = this._min.length; i < len; i++) {
        if (this._arr[this._min[i]] > x) {
          this._min.splice(i, 0, arrLen);
          return;
        }
      }
      this._min.push(arrLen);
    }
  }
  /**
   * @return {void}
   */
  pop() {
    this._min = this._min.filter(arrIndex => arrIndex !== this._arr.length - 1);
    this._arr.pop();
  }
  /**
   * @return {number}
   */
  top() {
    return this._arr[this._arr.length - 1];
  }
  /**
   * @return {number}
   */
  getMin() {
    return this._arr[this._min[0]];
  }
}

题解 2 - typescript

• 编辑时间：2021-07-19
• 执行用时：112ms
• 内存消耗：46MB
• 编程语言：typescript
• 解法介绍：储存单调栈。

class MinStack {
  private stack: number[] = [];
  private get topStack() {
    return this.stack[this.stack.length - 1];
  }
  private minStack: number[] = [];
  private get topMinStack() {
    return this.minStack[this.minStack.length - 1];
  }
  push(val: number): void {
    this.stack.push(val);
    if (this.minStack.length === 0 || this.topMinStack >= val) this.minStack.push(val);
  }
  pop(): void {
    if (this.topStack === this.topMinStack) this.minStack.pop();
    this.stack.pop();
  }
  top(): number {
    return this.topStack;
  }
  getMin(): number {
    return this.topMinStack;
  }
}