LeetCode第155题：最小栈

题干

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

• push(x) —— 将元素 x 推入栈中。
• pop() —— 删除栈顶的元素。
• top() —— 获取栈顶元素。
• getMin() —— 检索栈中的最小元素。

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/mi…
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：记录最小栈

其实刚开始我拿到题目一看觉得是十分容易的，无非就是找到最小值返回就可以了，但是事情肯定没有这么简单。效率属实不是很高。

所以我们可以使用这种方式：再专门设置一个记录最小栈的栈，每次添加时如果当前的val小于最小栈的栈顶元素，则将其设为栈顶，反之将当前的栈顶设为栈顶，此时栈顶依旧是最小值。所以当我们找最小值时只需要拿最小栈的栈顶元素即可。同时有人会担心删除元素怎么办，那就是两个栈同时出栈，不会引起混乱，因为当前的最小栈栈顶要么时我们主栈的栈顶。要么时主栈下面的元素。

代码实现：

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

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function (val) {
    let length1 = this.stack.length;
    let length2 = this.minStack.length;
    if (length1 == 0 && length2 == 0) {
        this.stack.push(val)
        this.minStack.push(val)
    } else {
        if (this.minStack[length2 - 1] > val) {
            this.minStack.push(val)
            this.stack.push(val)
        } else {
            this.minStack.push(this.minStack[length2 - 1])
            this.stack.push(val)
        }
    }
};

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

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

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

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