题目描述
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
分析
该题目要求实现一个带有返回当前栈中最小元素功能的数据结构，首先会想到使用一个变量保存当前最小元素的下标，但是仔细一想，如果当前最小元素刚好在栈顶，此时执行pop操作，那么最小元素会被弹出，新的最小元素又上哪儿找呢？比较暴力的方法是出现这种情况时，再遍历一遍栈就能重新得到最小元素的下标，但是这么暴力操作就没意思了而且时间复杂度很好。
可以使用双栈来实现min功能，栈1常规保存元素，栈2保存此时此刻的栈中最小 元素，比如说有元素进栈1，如果该元素小于栈2的栈顶元素，说明新的最小元素就是该进栈元素，否则，最小元素还是栈2的栈顶元素。
代码实现
var stack1 = []; var stack2 = []; function push(node) { if(stack2.length === 0 && stack1.length === 0){ stack1.push(node); stack2.push(node); } else{ stack1.push(node); var stack2Top = stack2[stack2.length-1]; if(node < stack2Top) stack2.push(node) else stack2.push(stack2Top); } } function pop() { stack2.pop(); return stack1.pop(); } function top() { return stack1[stack1.length-1]; } function min() { return stack2[stack2.length-1]; }
