最小栈

由于今天的每日一题比较简单，额外刷一下三叶姐这边的每日一题。

题目链接 (opens new window)

难度：中等

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

实现 MinStack 类:

MinStack() 初始化堆栈对象。

void push(int val) 将元素val推入堆栈。

void pop() 删除堆栈顶部的元素。

int top() 获取堆栈顶部的元素。

int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

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

提示：

-231 <= val <= 231 - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 104 次

目标是实现一个栈，他与普通的栈不同的是，可以返回栈里面最小的值。这道题能作为中等难度的题目，主要难点在于需要在常数时间内获取到最小值。

那既然题目要求方法getMin需要在常数时间得到最小值，我们只能在其他方法做文章了，比如push和pop。

一开始的想法是，用一个下标值来记录最小值的下标，但难点在于如何维护这个下标，如果是往栈添加元素还好，可以通过判断入栈的值与最小值做对比。但如果出栈的值刚好是最小值，那么得重新遍历一遍来查找最小值的下标，故放弃了这个想法。

然后又想到一个比较简单直接的思路是另外维护一个有序的队列，这样就能达到要求，但问题是原本的栈添加和删除元素的时候如何维护？

我原本的想法是，既然这个队列是有序的，那么可以通过二分查找快速定位添加和删除的元素的位置，这样维护的时间复杂度也不算高，只有O(logn)，而取最小值的时间复杂度也是O(1)。

但考虑到可能splice方法时间复杂度，那维护应该得算成O(n)。

class MinStack {
    private stack: number[];
    private minArray: number[];

    constructor() {
        this.stack = [];
        this.minArray = [];
    }

    push(val: number): void {
        this.stack.push(val);
        if (this.minArray.length === 0 || val < this.minArray[0]) {
            this.minArray.unshift(val);
        } else {
            const index = this.binarySearchInsert(val);
            this.minArray.splice(index, 0, val);
        }
    }

    pop(): void {
        if (this.stack.length === 0) return;
        const val = this.stack.pop();
        const index = this.binarySearch(val);
        if (index >= 0) {
            this.minArray.splice(index, 1);
        }
    }

    top(): number {
        if (this.stack.length === 0) return -1;
        return this.stack[this.stack.length - 1];
    }

    getMin(): number {
        if (this.minArray.length === 0) return -1;
        return this.minArray[0];
    }
    // 找到第一个比val大的元素的下标
    private binarySearchInsert(val: number): number {
        let left = 0, right = this.minArray.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (val < this.minArray[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    
    // 找到与val相同的元素的下标
    private binarySearch(val: number): number {
        let left = 0, right = this.minArray.length - 1;
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (val === this.minArray[mid]) {
                // 找到元素，向左继续查找第一个相同的元素
                let pos = mid;
                while (pos > 0 && this.minArray[pos - 1] === val) {
                    pos--;
                }
                return pos;
            } else if (val < this.minArray[mid]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

虽然可以解决，但是过程还是比较繁琐的。 然后看了一小眼题解，只能赞叹妙啊，用一个辅助栈，来记录当前栈中最小的值，并且维护的时间复杂度是O(1)。那么是如何维护的呢？

在原栈入栈时，辅助栈判断栈顶与入栈原值的大小，如果栈顶更小，则辅助栈入一个与栈顶相同的值，否则入栈原值。

这样的妙处是，辅助栈的栈顶一定是原栈中最小的值，并且原栈和辅助栈的高度相同。

更妙的地方是，原栈出栈的时候，辅助栈也跟着出栈，这样即使出栈的是当前的最小值，辅助栈的栈顶还是原栈的最小值，解决了我最开始记录最小值下标，出栈了最小值需要找到新的最小值的下标的难题。

class MinStack {
    private stack: number[]
    private min_stack: number[]

    constructor() {
        this.stack = []
        this.min_stack = []
    }

    push(val: number): void {
        this.stack.push(val)
        if (!this.min_stack.length) { // 一开始栈为空直接入栈即可
            this.min_stack.push(val)
        } else {
            this.min_stack.push(Math.min(val, this.min_stack[this.min_stack.length - 1]))
        }
    }

    pop(): void {
        this.stack.pop()
        this.min_stack.pop()
    }

    top(): number {
        return this.stack[this.stack.length - 1]
    }

    getMin(): number {
        return this.min_stack[this.min_stack.length - 1]
    }
}