题目描述：设计一个支持 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.

思路：初始化一个最小值变量，它的初始值可以设一个非常大的数（比如 Infinity），然后开始遍历整个栈。在遍历的过程中，如果遇到了更小的值，就把最小值变量更新为这个更小的值。这样遍历结束后，我们就能拿到栈中的最小值了。
这个过程中，我们对栈进行了一次遍历，时间复杂度无疑是 O(n)。

  1. /**
  2.  * 初始化你的栈结构
  3.  */
  4. const MinStack = function() {
  5.   this.stack = []
  6. };
  8. /** 
  9.  * @param {number} x
  10.  * @return {void}
  11.  */
  12. // 栈的入栈操作，其实就是数组的 push 方法
  13. MinStack.prototype.push = function(x) {
  14.   this.stack.push(x)
  15. };
  17. /**
  18.  * @return {void}
  19.  */
  20. // 栈的入栈操作，其实就是数组的 pop 方法
  21. MinStack.prototype.pop = function() {
  22.   this.stack.pop()
  23. };
  25. /**
  26.  * @return {number}
  27.  */
  28. // 取栈顶元素，咱们教过的哈，这里我本能地给它一个边界条件判断（其实不给也能通过，但是多做不错哈）
  29. MinStack.prototype.top = function() {
  30.   if(!this.stack || !this.stack.length) {
  31.       return 
  32.   }
  33.   return this.stack[this.stack.length - 1]
  34. };
  36. /**
  37.  * @return {number}
  38.  */
  39. // 按照一次遍历的思路取最小值
  40. MinStack.prototype.getMin = function() {
  41.     let minValue = Infinity  
  42.     const  { stack } = this
  43.     for(let i=0; i<stack.length;i++) {
  44.         if(stack[i] < minValue) {
  45.             minValue = stack[i]
  46.         }
  47.     }
  48.     return minValue
  49. };

时间复杂度 0(n)

时间效率更高的做法

增加一个栈 stack2 作为辅助栈

  1. const MinStack = function() {
  2.     this.stack = [];
  3.     // 定义辅助栈
  4.     this.stack2 = [];
  5. };
  7. /** 
  8.  * @param {number} x
  9.  * @return {void}
  10.  */
  11. MinStack.prototype.push = function(x) {
  12.     this.stack.push(x);
  13.     // 若入栈的值小于当前最小值，则推入辅助栈栈顶
  14.     if(this.stack2.length == 0 || this.stack2[this.stack2.length-1] >= x){
  15.         this.stack2.push(x);
  16.     }
  17. };
  19. /**
  20.  * @return {void}
  21.  */
  22. MinStack.prototype.pop = function() {
  23.     // 若出栈的值和当前最小值相等，那么辅助栈也要对栈顶元素进行出栈，确保最小值的有效性
  24.     if(this.stack.pop() == this.stack2[this.stack2.length-1]){
  25.         this.stack2.pop();
  26.     }
  27. };
  29. /**
  30.  * @return {number}
  31.  */
  32. MinStack.prototype.top = function() {
  33.     return this.stack[this.stack.length-1];
  34. };
  36. /**
  37.  * @return {number}
  38.  */
  39. MinStack.prototype.getMin = function() {
  40.     // 辅助栈的栈顶，存的就是目标中的最小值
  41.     return this.stack2[this.stack2.length-1];
  42. };

时间复杂度 0(1)