【程序员代码面试指南】二 栈和队列

由于个人兴趣，首文献给了「大数据和空间限制」一章。现在反过头来看书中的第一章「栈和队列」。

01 设计一个有getMin功能的栈

01.1 问题描述

实现一个功能正常的栈，并实现一个返回栈中最小元素的操作。

要求pop、push、getMin操作的时间复杂度都是$O$(1)。

注：$O$(1)代表一个常数。

01.2 笔者自己的弱智思路

一个栈就可以解决。

class Node<T>{
    T data;
    uint nextMinIndex = -1;
    uint preMinIndex = -1;
}

class GetMinStack<T>{
    Stack<Node<T>> s;
    uint minIndex;
}

当入栈时，比较将入栈元素和int curMin = s[minIndex]的大小：

• 如果比curMin小，那么入栈，并设置当前Node的nextMinIndex为minIndex，然后更新minIndex为栈顶
• 如果比curMin大，那么一路循环，找到比它小的节点，插入到该节点的前一个节点的nextMinIndex上，复杂度为$O$(n)，不符合要求

出栈时，将栈顶从链表中扯出来，根据nextMinIndex和preMinIndex把前后节点连在一起。

当执行getMin()时，直接返回minIndex。

该弱智方法的缺陷就是插入的时候时间复杂度为$O$(n)。

01.2 作者的睿智思路

准备两个栈，一个名为stackData，作为普通栈使用，另一个名为stackMin，栈顶永远是最小值。

入栈规则：

规定新进来的数字为newNum，先将其压入stackData，然后判断stackMin是否为空

1. 如果stackMin为空，那么压入stackMin作为栈顶
2. 如果stackMin不为空，那么比较newNum和stackMin的栈顶
3. 如果newNum <= 栈顶，那么压入stackMin
4. 否则不做操作

此举可以保证stackMin栈顶永远最小。

出栈规则：

1. 从stackData出栈
2. 比较出栈的value和stackMin和栈顶
3. 当value == stackMin.top的时候，从stackMin出栈
4. 否则啥事儿不做

关键：

比stackMin栈顶大的并不会入栈（比栈顶大的一律被忽略），导致stackMin的栈顶必然小于等于stackData栈顶。stackData出栈的时候同步出栈stackMin即可。

比起笔者弱智方法的好处

其实算是个改进版。笔者的弱智方法想的是用一个数永远来记录最小值，当stackData有出栈需求的时候就变得很蛋疼了，因为没法获取下一个最小值。为了能够渐进地获取最小值，当然就需要另一个栈。

接下来的问题就是判断何时需要把数字压到另一个栈里面。

在笔者的弱智方法中需要考虑一个问题，就是当一个数字出栈之后，是否会影响最小值。而作者思路的关键是，一旦出栈这个数字大于stackMin的栈顶，那么它必然不是最小值，可以安全出栈而不用考虑其他因素。

作者的思路其实将stackData分为一段一段，并将每一段的最小值记录在stackMin中。

假设我们压入3、4、5、1、2。最终被压入stackMin的就是3和1，将stackData分为了两段，在3之后1之前，以及1到栈顶之间的都可以安全出栈。