实现栈获取最小值的方法，要求时间复杂度为O(1)

在上一篇介绍栈数据结构的文章前端也要懂的数据结构(1)--栈中，我留下了一个问题：如何实现一个栈的方法，它能够返回栈的最小值且时间复杂度为O(1)。今天我们来说说几种解决问题的方式。

结合栈的数据结构和先入后出的特点，如果想实现复杂度为O(1)的取最小值的方法，就要把最小值保存起来。而且还要随着出栈，入栈的进行，不断的更新最小值。下面介绍一下我想到的几种方法：

1.解法A

思路：每次入栈和出栈同时操作两个元素，下面的元素是需要入栈的元素，上面的元素是整个栈的最小元素。

同时入栈两个元素

在入栈之前先获取栈顶元素，也就是入栈之前的最小元素。将当前最小元素和入栈的元素比较，如果入栈的元素更小，则最小元素为入栈元素，如果入栈元素大于当前最小元素，则最小元素不变。

演示

下面就用JavaScript数组来实现这样的一个栈。

var stack = {
  //用数组存储元素
  items : [],
  //实现入栈方法 add
  add: function(element){
    //如果数组内没有元素，则最小元素就是入栈的元素
    if(stack.items.length === 0){
      stack.items.push(element);
      stack.items.push(element);
    }else{
      //获取当前最小元素
      var minElement = stack.getMinElement();

      if(element < minElement){
        minElement = element;
      }

      stack.items.push(element);
      stack.items.push(minElement);
    }
  },
  //实现出栈的方法
  remove: function(){
    stack.items.pop();
    return stack.items.pop();
  },

  getMinElement: function(){
    if(stack.items.length === 0){
      return null;
    }else{
      return stack.items[stack.items.length-1];
    }
  }
};

测试结果：

image.png

1.解法B

思路：同时维护两个栈，一个用来存储元素，另一个来存储最小值。两个栈同步更新，这样就能实现获取最小值的功能。

元素栈 最小值栈

JavaScript实现如下：

var stack = {
  //用数组存储元素
  items: [],
  mins:[],
  //实现入栈方法 add
  add: function(element){
    //如果数组内没有元素，则最小元素就是入栈的元素
    if(stack.items.length === 0){
      stack.items.push(element);
      stack.mins.push(element);
    }else{
      //获取当前最小元素
      var minElement = stack.getMinElement();

      if(element < minElement){
        minElement = element;
      }
      stack.items.push(element);
      stack.mins.push(minElement);
    }
  },
  //实现出栈的方法
  remove: function(){
    stack.mins.pop();
    return stack.items.pop();
  },

  getMinElement: function(){
    if(stack.items.length === 0){
      return null;
    }else{
      return stack.mins[stack.mins.length-1];
    }
  }
};

stack.add(1);
stack.add(2);
stack.getMinElement();

测试结果：

测试

大家如果有其他的解法，欢迎交流讨论~

往期文章推荐：
左右脑测试小程序的真正逻辑
JS-判断变量是否为数组
BootStrap栅格布局的实现
CSS-绘制各种基本图形