题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数（时间复杂度应为 O（1））

注意：保证测试中不会当栈为空的时候，对栈调用 pop()或者 min()或者 top()方法

提示：

各函数的调用总次数不超过 20000 次

测试用例

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2.

代码实现

/**
 * initialize your data structure here.
 */
function MinStack() {
  this.stack = [];

  // 存储栈中最小元素
  this.minstack = [];

  // 使用两个栈来实现MinStack

  // 普通栈
}

/**
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function (x) {
  // 普通栈入栈
  this.stack.push(x);
  // 最小栈入栈
  if (
    this.minstack.length == 0 ||
    x <= this.minstack[this.minstack.length - 1]
  ) {
    this.minstack.push(x);
  }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function () {
  // 普通栈出栈
  let cur = this.stack.pop();
  // 判断出栈的是不是最小值
  if (cur === this.minstack[this.minstack.length - 1]) {
    this.minstack.pop();
  }
  return cur;
};

/**
 * @return {number}
 */
MinStack.prototype.top = function () {
  return this.stack[this.stack.length - 1];
};

/**
 * @return {number}
 */
MinStack.prototype.min = function () {
  return this.minstack[this.minstack.length - 1];
};

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

let minStack = new MinStack();

console.log(minStack.push(-2));
console.log(minStack.push(0));
console.log(minStack.push(-3));
console.log(minStack.min());
console.log(minStack.pop());
console.log(minStack.top());
console.log(minStack.min());

/* 
  undefined
  undefined
  undefined
  -3
  -3
  0
  -2
*/