【剑指offer】20 包含min函数的栈

题目描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O(1)）。

解法分析

一般来说返回最小值需要遍历整个栈，时间复杂度为O(n)，不满足题目要求的O(1)，因此我们需要考虑使用其他方法，加个辅助栈用于存放最小元素，每次有元素进栈就与辅助栈元素作对比。

代码

 1 var minStack = [];
 2 var dataStack = [];
 3 function push(node)
 4 {
 5     // write code here
 6     dataStack.push(node);
 7     if(minStack.length == 0 || node < minStack[minStack.length-1]){
 8         minStack.push(node);
 9     }else{
10         minStack.push(minStack[minStack.length-1]);
11     }
12 }
13 function pop()
14 {
15     // write code here
16     if(minStack.length > 0 && dataStack.length >0){
17         minStack.pop();
18         dataStack.pop();
19     }
20     
21 }
22 function top()
23 {
24     // write code here
25     if(dataStack.length > 0) return dataStack[dataStack.length-1];
26 }
27 function min()
28 {
29     // write code here
30     if(dataStack.length > 0 && minStack.length > 0) return minStack[minStack.length-1];
31 }

执行结果