栈 + 动态规划 - 解决栈变化时原地获取该栈最小元素的问题

想要随时取到当前栈中最小的元素，我们不妨另建一个栈，用来存放当原始栈含 n 个元素时，对应的栈中的最小元素（如下图）。

可以看出，上图中的最小栈，是满足题目要求的，它总能保证我们可以原地获取当前原始栈中的最小元素（那就是最小栈栈顶的元素）。 我们先不去想如何从零开始实现这样一个最小栈，而是不妨先假设手头已经存在了这样一个最小栈，它有两个很重要的性质：

1. 最小栈的高度与原始栈的高度恒等；
2. 最小栈的栈顶元素是当前对应的原始栈中的最小元素。

现在我们要思考的问题是，当原始栈进行出/入栈操作时，怎么保证最小栈依然满足这两个性质。

情景一：原始栈入栈

为了保证最小栈的高度与原始栈相同，最小栈也要入栈一个元素，同时要保证这个元素是入栈后的原始栈中的最小元素。你可能有点儿挠头，我怎么知道最小栈要入栈什么元素？别急，想想最小栈的两个性质（我们是在假定已有一个最小栈的基础上进行情景思考的），对喽，现在最小栈栈顶的元素，是原始栈入栈前对应的最小元素~ 那么我们只要把入栈的元素和最小栈栈顶的元素进行比较就可以知道该把谁推进最小栈中啦~

情景二：原始栈出栈 这时候最小栈只要开开心心得和原始栈一起做一个出栈动作就可以，你肯定可以想到为什么。

当你在着手实现上述功能的代码的时候，会惊奇的发现，最小栈原来一开始就在那里！为什么呢？因为一开始原始栈是空的，最小栈也是空的，最小栈一开始就是最小栈~

别忘了边界条件哟，主要是对空值的判断，还是很 easy 滴，读一读代码相信你就了然。

代码如下：

var stack = [];	// 原始栈
var stackMin = [];	// 最小栈
function push ( node ) {
  	// 入栈的操作，即是我们对最小栈进行操作的时机
    if (stack.length === 0) {	// 最小栈
        stackMin.push(node);
    } else {
        if (node <= stackMin[stackMin.length - 1]) {
            stackMin.push(node);
        } else {
            stackMin.push(stackMin[stackMin.length - 1]);
        }
    } 
    stack.push(node);
}
function pop () {
    if (stack.length === 0) {
        return null;
    } else {
        stackMin.pop();
        let ret = stack.pop();
        return ret;
    }
}
function top () {
    let n = stack.length;
    if (n === 0) {
        return null;
    } else {
        return stack[n - 1];
    }
}
function min () {
    let ret = stackMin[stackMin.length - 1];
    return ret;
}
module.exports = {
    push : push,
    pop : pop,
    top : top,
    min : min
};