设计一个最小栈

[vivatoviva]

题目出处

这道题目来自leetcode

题目要求

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

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

示例:

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

题目分析

首先分析题目的要求可知：题目要求一个栈的数据结构，但是有一个要求就是需要在常数时间内找出堆栈中的最小元素

第一种实现思路是将每个栈元素扩展成双向链表的节点，然后按照大小顺序将各个节点连接起来，剩下的一些操作将按照栈的操作来进行

第二种实现思路使用两个栈来实现题目要求，一个栈按照顺序来存储出现的最小值，另一个栈存储出现过的最小值

第三种实现思路只需要使用一个栈来实现题目，每次push新的元素将向栈中推两个元素，一个是栈前面最小的节点，另一个是当前推入的元素，这种插入方式将导致每次插入两个元素，第一个是当前栈中最小的元素，另一个当前插入的元素

具体实现

• 采用第二种实现思路

Array.prototype.last = function (params) {
  const length = this.length;
  if (length) {
    return this[length - 1];
  }
  return false;
}
/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.stack = []; // 保存正常顺序的栈
    this.minStack = []; // 保存最小数据的栈
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack.push(x);
    const minValue = this.minStack.last();
    if (minValue === false) {
      this.minStack.push(x);
    } else {
      if (x <= minValue) {
        this.minStack.push(x);
      }
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    const popValue = this.stack.pop();
    if (popValue === this.minStack.last()) {
      this.minStack.pop();
    }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stack.last();
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
  return this.minStack.last();
};

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