20.包含min函数的栈

《剑指Offer》刷题GitHub链接

题目描述

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

解题思路

这里采用了+多一个栈来存放最小值的方法。我看到的有两种解法：

1. 当node < stack2的最后一个值时，才push进来，那么pop的时候就需要验证stack1 pop出来的那个值是否等于stack2的最后一个值（也就是最小值）

2. push进来时，无论如何都会push一个值进stack2，node小就push node，原来的stack2最后一个值小就push原来的最小值，这样做的好处是pop的时候不需要判断，直接两个栈都pop一下就ok了，stack2上的值都是对应的stack1上的值得最小值，很方便，所以我采用了这种思路。

Code

var stack1 = [];
var stack2 = [];

function push(node)
{
    // write code here
    if(stack1.length == 0 && stack2.length == 0){
        stack1.push(node);
        stack2.push(node);
    }else{
        stack1.push(node);
        var min = stack2[stack2.length-1];
        if(node < min){
            stack2.push(node);
        }else{
            stack2.push(min);
        }
    }
}
function pop()
{
    // write code here
    stack2.pop();
    return stack1.pop();
}
function top()
{
    // write code here
    return stack1[stack1.length-1];
}
function min()
{
    // write code here
    return stack2[stack2.length-1];
}