Description

算法步骤

1. 用两个栈，一个栈st用来放数字，一个栈minSt用来放当前的最小值。
2. 数入栈时，如果minSt为空，或者minSt的栈顶元素大于等于要入栈的数字，那么在入栈st的同时，在minSt中入栈该数字。表示当前为止的最小值。
3. 数出栈时，如果出栈的数字就是minSt的栈顶元素，那么在出栈st的同时，在minSt中出栈该数字。
4. 获取当前最小值时，直接返回minSt的栈顶元素。

总结

• 无法用一个变量来保存当前的最小值，因为当最小值出栈后，无法知道下一个最小值是多少。
• minSt相当于存储历史最小值，当最小值出栈后，minSt的栈顶元素就是下一个最小值。
• minSt实际上是一个单调递减栈。

class MinStack {
  private minSt: number[] = [];
  private st: number[] = [];

  push(val: number): void {
    const minSt = this.minSt;
    this.st.push(val);

    if (minSt.length === 0 || minSt[minSt.length - 1] >= val) {
      minSt.push(val);
    }
  }

  pop(): void {
    const minSt = this.minSt;
    const top = this.st.pop()!;

    if (top === minSt[minSt.length - 1]) {
      minSt.pop();
    }
  }

  top(): number {
    return this.st[this.st.length - 1]!;
  }

  getMin(): number {
    return this.minSt[this.minSt.length - 1]!;
  }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(val)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */
Copy