2020-06-01 前端算法-最小元素的栈

LeetCode 第115题

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。


输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

/*
思路: stackMinList为存储最小值的数组,使用同步加同步减的思路,
stackList进来的新元素比stackMinList的top元素大则无视,
否则stackMinList顶部的元素变成刚刚进来的小值。
*/

var MinStack = function() {
  this.stackList = [];
  this.stackMinList = [];
};

MinStack.prototype.toString = function() {
  console.log('stackList: ', this.stackList)
  console.log('stackMinList: ', this.stackMinList)
}

/**
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
  //同步加同步减push pop
  this.stackList.push(x);

  // stack存储最小值的集合
  if (this.stackMinList.length === 0) {
    this.stackMinList.push(x);
  } else {
    // 将最小值压入栈顶
    let temp = this.stackMinList[this.stackMinList.length - 1];
    if (x < temp) {
      this.stackMinList.push(x);
    } else {
      this.stackMinList.push(temp);
    }
  }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
  if (this.stackList.length) {
    this.stackList.pop();
    this.stackMinList.pop();
  }
};

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

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

const minStack = new MinStack();

minStack.push(1);
minStack.push(2);
minStack.push(0);
minStack.push(4);
minStack.push(5);

console.log(minStack);

minStack.pop();

console.log(minStack);