1. 题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

  1. MinStack minStack = new MinStack();
  2. minStack.push(-2);
  3. minStack.push(0);
  4. minStack.push(-3);
  5. minStack.min();   --> 返回 -3.
  6. minStack.pop();
  7. minStack.top();      --> 返回 0.
  8. minStack.min();   --> 返回 -2.

提示：

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

    2. 解题思路

    这里我们需要保存一个最小值，所以在每次push一个新的值时，可以push一个对象。对象中包含两个属性，分别是这次push的值和当前栈中最小的值，并且要保持这个最小值是最新的，这样最后一个值push完成之后，和他一起的最小值就是当前队列中的最小值。

复杂度分析：

  • 时间复杂度：O(1)， push(), pop(), top(), min() 方法的时间复杂度均为常数级别；
  • 空间复杂度：O(N)， 这里需要一个长度为N的栈来保存每个值对应的对象。

    3. 代码实现

    ```typescript /**
    • initialize your data structure here. */ var MinStack = function() { this.stack = []; };

/**

  • @param {number} x
  • @return {void} */ MinStack.prototype.push = function(x) { this.stack.push({
    1.  val: x,
    2.  min: this.stack.length ? Math.min(x, this.min()) : x,
    }) };

/**

  • @return {void} */ MinStack.prototype.pop = function() { this.stack.pop() };

/**

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

/**

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

/**

  • 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() */ ```

    4. 提交结果

    image.png