在上一篇介绍栈数据结构的文章前端也要懂的数据结构(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-绘制各种基本图形
