155.最小栈.md

LeetCode-155 最小栈

难度： 简单

类型：栈

题目：

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

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

示例：

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.

思路：

getMin 方法是考察的重点。

通常找出数组中的最小值的思路是： 定义一个初始化变量， 将这个初始化变量定义为一个很大的值，例如 Infinity。 然后循环遍历数组，每次比较元素与初始值的大小，每次都将较小的值赋值给这个初始变量，最终遍历完成得到的值就是数组中的最小值。

但这样做的时间复杂度是 O(n)

const arr = [10, 11, 2, 3, 4, 5, 6]

let minValue = Infinity
for (let i =0; i < arr.length; i++) {
    if (arr[i] < minValue) {
        minValue = arr[i]
    }
}
console.log(minValue)

优化： O(1) 用空间换时间

额外创建一个辅助的栈， 始终让这个辅助栈从栈底到栈顶保持一个逐渐递减的趋势。

当获取最小值的时候，辅助栈的栈顶就是最小值。

当 push 的时候，判断 push 的元素是否比辅助栈栈顶的小或者相等，如果是，则推入辅助栈。

当 pop 的时候，判断 pop 的元素是否和辅助栈栈顶的元素相等，如果是，则出辅助栈，保证最小值的有效性

实现：

JavaScript:

function MinStack () {
    this.stack = []
    this.stack2 = []
}

MinStack.prototype.push = function (val) {
    this.stack.push(val)
    if (!this.stack2.length || this.stack2[this.stack2.length-1] >= val) {
        this.stack2.push(val)
    }
}

MinStack.prototype.pop = function () {
    if (this.stack.pop() === this.stack2[this.stack2.length-1]) {
        this.stack2.pop()
    }
}

MinStack.prototype.top = function () {
    return this.stack[this.stack.length-1]
}

// 辅助栈的设计主要是为了 getMin 服务
MinStack.prototype.getMin = function (val) {
    return this.stack2[this.stack2.length-1]
}