最小栈

[Cosen95]

leetcode: https://leetcode-cn.com/problems/min-stack/

[Cosen95]

这道题目中，其中前三个操作：push、pop 和 top，数组本身已经提供，我们需要关心的是getMin ，也就是检索栈中的最小元素。

我们很快能想到的一种思路是：初始化一个最小值变量，它的初始值可以设一个非常大的数（比如 Infinity），然后开始遍历整个栈。在遍历的过程中，如果遇到了更小的值，就把最小值变量更新为这个更小的值。这样遍历结束后，我们就能拿到栈中的最小值了。

对应编码实现：

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    // 初始化栈
    this.stack = []
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack.push(x)
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    this.stack.pop()
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    if(!this.stack || !this.stack.length) {
        return
    }
    return this.stack[this.stack.length - 1]
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    let min = Infinity;
    const { stack } = this;
    for(let i = 0;i < stack.length;i++) {
        if(stack[i] < min) {
            min = stack[i]
        }
    }
    return min
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */

这个过程中，我们对栈进行了一次遍历，时间复杂度无疑是 O(n)。

有没有更好的方案呢？

改善时间复杂度的一个很重要的策略就是时间换空间。

我们可以考虑再搞个栈（stack2）出来作为辅助，让这个栈去容纳当前的最小值。

如何确保 stack2 能够确切地给我们提供最小值？ 这里我们需要实现的是一个从栈底到栈顶呈递减趋势的栈：

• 取最小值：由于整个栈从栈底到栈顶递减，因此栈顶元素就是最小元素。
• 若有新元素入栈：判断是不是比栈顶元素还要小，否则不准进入 stack2。
• 若有元素出栈：判断是不是和栈顶元素相等，如果是的话，stack2 也要出栈。

按照这个思路，我们可以有以下编码：

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    // 初始化栈
    this.stack = [];
    this.stack2 = [];
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack.push(x);
    // stack2 从栈底到栈顶递减 判断当前新增元素小于等于stack2中的最小元素 才可以入栈
    if(this.stack2.length === 0 || this.stack2[this.stack2.length - 1] >= x) {
        this.stack2.push(x)
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    if(this.stack.pop() === this.stack2[this.stack2.length - 1]) {
        this.stack2.pop()
    }

};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    if(!this.stack || !this.stack.length) {
        return
    }
    return this.stack[this.stack.length - 1]
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.stack2[this.stack2.length - 1]
};

/**
 * Your MinStack object will be instantiated and called as such:
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.getMin()
 */