数据结构与算法面试宝典 - 前微软资深软件工程师 - 拉勾教育
今天我们开始学习一个在工作，以及面试中经常被问到的一个数据结构——栈。
栈这种数据结构，在计算机中有着广泛地运用，比如编程语言中函数的调用、操作系统中从用户态到内核态寄存器的保存、网络消息的处理等都会用到栈。
今天我们主要介绍面试中经常考察的栈相关的高频题目，主要内容包含两方面：
- 栈的特性与使用
- 单调栈的解题技巧
针对一道题目，我会深度讲解一种解法，以及其变型，并且带你总结同类问题的解题技巧和规律，从而解决多种相似及变形题目。并且，我会给出 Java/C++/Python 三种代码示例，方便你学习。现在，开始我们的旅程与探险！
栈的特性与使用
简单栈的特点可以用一句话来概括，先进后出（LIFO）顺序。比如 Java 代码（解析在注释里）：
Stack<Character> t = new Stack<Character>();t.push('a');t.push('b');t.peek();t.pop();t.peek();t.pop();
这部分代码片段执行效果如下图所示：
那么如何深度利用栈的 “先进后出” 特点来解决实际工作和面试中的问题呢？是否可以总结出什么有用的知识技巧？现在你的大脑里可能已经有了一个栈的 “萌芽”，如下图所示：
接下来我将通过大厂面试题，带你学习这块重点知识。经过不断地 “浇灌”，栈这棵“萌芽” 才能抽枝散叶，长得更加茁壮。
例 1：判断字符串括号是否合法
【题目】字符串中只有字符’(‘和’)’。合法字符串需要括号可以配对。比如：
输入：”()”
输出：true
解释：()，()()，(()) 是合法的。)(，()(，(() 是非法的。
请你实现一个函数，来判断给定的字符串是否合法。
boolean isValid(String s);
【分析】虽然这是一道简单题，但是我们依然可以拿它来训练深度思考的能力。如果你已经知道答案，或者说能够轻松地解决这道题，不妨再跟我一起看看如何拆解这道题。
首先，分析题目的时候，要特别注意以下 4 点，归纳为 “四步分析法”。
- 模拟：模拟题目的运行。
- 规律：尝试总结出题目的一般规律和特点。
- 匹配：找到符合这些特点的数据结构与算法。
- 边界：考虑特殊情况。
接下来我们就按照上面的步骤来拆解题目。
1. 模拟
首先我们以字符串 s = “()()(())”，进行模拟，如下动图所示：
2. 规律
我们回顾一下模拟过程，可以总结出以下 3 个特点。
（1）每个左括号’(‘或者右括号’)’都完成配对，才是合法的。
（2）配对可以通过消除法来消掉合法的括号，如果最后没有任何字符了，那么就是合法字符串。
（3）奇数长度的字符串总是非法的。
3. 匹配
到这里，我们已经弄清楚题目考核的重点，就是消除法的模拟。如果仔细观察消除法的行为模式，你会发现，在消除的时候，上图中红色的部分和栈的行为非常像。因此，可以用栈来进行消除法的模拟。
4. 边界
当我们找到问题匹配的算法或者数据结构之后，一定要记住，接下来一步并不是马上写代码，而是要考虑一些边界问题，也就是一些特殊情况：
- 字符串为空
- 字符串只有 1 个或者奇数个
- 字符串是 “(((())))” 嵌套很多层的是否可以处理
【画图】可以采用画图的方法来判断自己是否已经了解题目，或者是否能灵活运用一个算法。在面试中经常需要在白板或者纸上画图，所以在学习算法时候建议你培养多画图的习惯。
- 当遇到左括号’(‘时，进行压栈操作
- 当遇到右括号’)’时，进行弹栈操作
为了帮助你更好地理解，我将求解过程制作成一张动图，如下所示，注意左边栈的变化。
【代码】到这里时，你可以写出以下核心代码（解析在注释里）：
boolean isValid(String s) {if (s == null || s.length() == 0) {return true;}if (s.length() % 2 == 1) {return false;}Stack<Character> t = new Stack<Character>();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c == '(') {t.push(c);} else if (c == ')') {if (t.empty()) {return false;}t.pop();}return t.empty();}
复杂度分析：每个字符只入栈一次，出栈一次，所以时间复杂度为 O(N)，而空间复杂度为 O(N)，因为最差情况下可能会把整个字符串都入栈。
做完一道题后，我们还需要从两个角度进行深度思考：
- 深度，比如这种解法还可以怎么优化呢？
- 广度，比如这种解法具有普适性吗？可以推广吗？
1. 深度扩展
如果仔细观察，你会发现，栈中存放的元素是一样的。全部都是左括号’(‘，除此之外，再也没有别的元素，优化方法如下。
栈中元素都相同时，实际上没有必要使用栈，只需要记录栈中元素个数。 我们可以通过画图来解决这个问题，如下动图所示：
实际上，就是把入栈与出栈变成了 leftBraceNumber 的加减。代码如下（解析在注释里）：
public boolean isValid(String s) {if (s == null || s.length() == 0) {return true;}if (s.length() % 2 == 1) {return false;}int leftBraceNumber = 0;for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c == '(') {leftBraceNumber++;} else if (c == ')') {if (leftBraceNumber <= 0) {return false;}--leftBraceNumber;}}return leftBraceNumber == 0;}
复杂度分析：每个字符只入栈一次，出栈一次，所以时间复杂度为 O(N)，而空间复杂度为 O(1)，因为我们已经只用一个变量来记录栈中的内容。
【小结】经过前面的分析，现在我们可以将题目的特点做一下小结：
2. 广度扩展
接下来再来看看如何进行广度扩展。观察题目可以发现，栈中只存放了一个维度的信息：左括号’(‘和右括号’)’。如果栈中的内容变得更加丰富一点，就可以得到下面这道扩展题。
【题目扩展】给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合
- 左括号必须以正确的顺序闭合
- 注意空字符串可被认为是有效字符串
请实现接口： public boolean isValid(String s)
对于这道题，我希望你能再走一下：分析，画图，代码，扩展，小结的五步曲。
【小结】接下来，我们对拓展题目进行总结，希望你从中提炼出经验，以后再遇到相似的题目能够轻松应对。
对于栈的使用，除了知道 “后进先出” 这个规律，我们还可以帮它长出一些叶子来，如下图所示：
因此，以后你在看到题目中类似配对、消除之类的动作时，可以采用栈来操作。通过这两个方向上的整理和归纳，我们进一步探寻到了题目和解法之间的联系。让我们继续前进。
例 2：大鱼吃小鱼
【题目】在水中有许多鱼，可以认为这些鱼停放在 x 轴上。再给定两个数组 Size，Dir，Size[i] 表示第 i 条鱼的大小，Dir[i] 表示鱼的方向 （0 表示向左游，1 表示向右游）。这两个数组分别表示鱼的大小和游动的方向，并且两个数组的长度相等。鱼的行为符合以下几个条件:
- 所有的鱼都同时开始游动，每次按照鱼的方向，都游动一个单位距离；
- 当方向相对时，大鱼会吃掉小鱼；
- 鱼的大小都不一样。
输入：Size = [4, 2, 5, 3, 1], Dir = [1, 1, 0, 0, 0]
输出：3
请完成以下接口来计算还剩下几条鱼？
int solution(int[] Size, int[] Dir);
题目的示意图如下所示：
【分析】对于这道题而言，大鱼吃掉小鱼的时候，可以认为是一种消除行为。只不过与括号匹配时的行为不一样：
- 括号匹配是会同时把左括号与右括号消除掉；
- 大鱼吃小鱼，只会把小鱼消除掉。
1. 模拟
首先我们以如下示例进行演示：
Size = [4, 3, 2, 1 5], Dir = [0, 1, 0, 0, 0]
注意：当鱼的游动方向相同，或者相反时，并不会相遇，此时大鱼不能吃掉小鱼。
2. 规律
通过模拟，可以发现如下规律:
- 如果两条鱼相对而游时，那么较小的鱼会被吃掉；
- 其他情况没有鱼被吃掉。
3. 匹配
我们发现，下面活下来的鱼的行为（上图红框部分）就是一个栈。每当有新的鱼要进来的时候，就会与栈顶的鱼进行比较。那么我们匹配到的算法就是栈了。
4. 边界
在正式开始求解之前，我们还是想一想两种边界：
- 所有的鱼都朝着一个方向游；
- 一条鱼吃掉了其他的所有鱼。
我们在后面设计算法的时候，这些情况都需要考虑到。
【画图】这道题的关键仍然是如何使用栈来模拟鱼的消除行为。接下来我们用栈画一下图，演示出我们的思路，动图如下：
【代码】根据之前的思考，可以得到如下解法（解析在注释里）：
int solution(int[] fishSize, int[] fishDirection) {final int fishNumber = fishSize.length;if (fishNumber <= 1) {return fishNumber;}final int left = 0;final int right = 1;Stack<Integer> t = new Stack();for (int i = 0; i < fishNumber; i++) {final int curFishDirection = fishDirection[i];final int curFishSize = fishSize[i];boolean hasEat = false;while (!t.empty() && fishDirection[t.peek()] == right &&curFishDirection == left) {if (fishSize[t.peek()] > curFishSize) {hasEat = true;break;}t.pop();}if (!hasEat) {t.push(i);}}return t.size();}
复杂度分析：每只鱼只入栈一次，出栈一次，所以时间复杂度 为 O(N)，而空间复杂度为 O(N)，因为最差情况下可能把所有的鱼都入栈。
【小结】接下来我们一起对这道题做一下归纳。可以发现，与例 1 相比，它们的消除行为有所不同：
- 在例 1 中，消除行为表现为配对的两者都会消除；
- 在例 2 中，消除行为表现为配对的两者中有一个会被消除。
此外，在与 例 1 的比较中，可以发现，栈中的内容也有所不同：
- 在例 1 中，栈中的存放的就是内容本身；
- 在例 2 中，栈中存放的只是内容的索引，可以通过索引得到内容。
再者，我们也发现，在弹栈的时候，不再像以前那样，每次只弹一个元素，而是采用了 while 循环，要一直弹到满足某个条件为止。所以我们总结出，弹栈的时候有两种情况：
- 弹一个元素就可以；
- 用 while 语句一直弹，直到满足某个条件为止。
因此，这道题的考点我们也挖掘出来了：
- 是否会用栈来存放索引？
- 是否想到在弹栈的时候一定要满足某个条件才停止弹栈？
到这里栈的特点更丰富了，通过我们不断地浇灌也让栈这棵 “萌芽” 长出了更多的叶子，总结如下图所示：
单调栈的解题技巧
大部分数据结构书上都不太会讲单调栈的知识，但是在面试中却经常考察这一类题，这就非常考验你的知识储备了。
首先我们看一下单调栈的定义：单调栈就是指栈中的元素必须是按照升序排列的栈，或者是降序排列的栈。对于这两种排序方式的栈，还给它们各自取了小名。
升序排列的栈称为递增栈，如下图所示：
降序排列的栈称为递减栈，如下图所示：
注意：示意图所展示的这两种栈是横向排列的。栈中元素的值，分别用不同高度的矩形来表示，值越大，矩形越高。
接下来我们介绍一下递增栈的有序性，一句话：“任何时候都需要保证栈的有序性”。
递增栈的特性可以演示如下（上方数组是要依次入栈的元素）：
递减栈的特性可以演示如下：
通过这两个动图，我们可以总结出单调栈的特点，如下图所示：
接下来我们通过一些小题目来对单调栈进行 “浇灌”，也让单调栈长出更多的 “叶子”。
例 3：找出数组中右边比我小的元素
【题目】一个整数数组 A，找到每个元素：右边第一个比我小的下标位置，没有则用 -1 表示。
输入：[5, 2]
输出：[1, -1]
解释：因为元素 5 的右边离我最近且比我小的位置应该是 A[1]，最后一个元素 2 右边没有比 2 小的元素，所以应该输出 -1。
接口：int[] findRightSmall(int[] A);
【分析】每次开始分析题意时，记得要拿出我们的 “四步分析法”，通过一步步分析找到题目相应的解法。
1. 模拟
在正式开始上手之后，我们先拿两个例子演示一下，看看能不能发现题目中隐藏的一些有趣规律，动图如下所示：
2. 规律
这里我们是照着题意去寻找一个右边比它小的数的下标。可以发现，A[4] = 4 及 A[5] = 0，这两个数字多次被用到。并且：
- A[4] 发现有左边 A[3]，A[3] 就匹配成功；
- 结合 A[5] = 0 的例子，我们发现它会把比它大的数都进行匹配成功，但是 A[3] 除外；
- A[3] 可以认为是匹配成功之后，被 A[4]消除了。
这时可以总结出：一个数总是想与左边比它大的数进行匹配，匹配到了之后，小的数会消除掉大的数。
3. 匹配
当你发现要解决的题目有两个特点：
- 小的数要与大的数配对
- 小的数会消除大的数
你的脑海里应该联想到关于单调栈的特性。下面我们看看如何利用单调栈解决这道题目。
【画图】在这里，依然需要画一个图来描述一下我们的思路及想法，如下图所示：（红色部分表示栈，我们只将下标绿色值放到栈中，为了看图方便，把下标对应的值也标在了相应位置。）
Step 1. 首先将 A[0] = 1 的下标 0 入栈。
Step 2. 将 A[1] = 2 的下标 1 入栈。满足单调栈。
Step 3. 将 A[2] = 4 的下标 2 入栈。满足单调栈。
Step 4. 将 A[3] = 9 的下标 3 入栈。满足单调栈。
Step 5. 将 A[4] = 4 的下标 4 入栈时，不满足单调性，需要将 A[3] = 9 从栈中弹出去。下标 4 将栈中下标 3 弹出栈，记录 A[3] 右边更小的是 index = 4。
Step 6. 将 A[5] = 0 的下标 5 入栈时，不满足单调性，需要将 A[4] = 4 从栈中弹出去。下标 5 将下标 4 弹出栈，记录 A[4] 右边更小的是 index = 5。A[5] = 0 会将栈中的下标 0, 1, 2 都弹出栈，因此也需要记录相应下标右边比其小的下标为 5，再将 A[5] = 0 的下标 5 放入栈中。
Step 7. 将 A[6] = 5 的下标 6 放入栈中。满足单调性。
Step 8. 此时，再也没有元素要入栈了，那么栈中的元素右边没有比其更小的元素。因此设置为 -1.
【代码】到此为止，相信你已经可以根据思路写出代码了，代码如下（解析在注释里）：
public static int[] findRightSmall(int[] A) {int[] ans = new int[A.length];Stack<Integer> t = new Stack();for (int i = 0; i < A.length; i++) {final int x = A[i];while (!t.empty() && A[t.peek()] > x) {ans[t.peek()] = i;t.pop();}t.push(i);}while (!t.empty()) {ans[t.peek()] = -1;t.pop();}return ans;}
复杂度分析：每个元素只入栈一次，出栈一次，所以时间复杂度为 O(N)，而空间复杂度为 O(N)，因为最差情况可能会把所有的元素都入栈。
【小结】到这里我们可以得到一个有趣且非常有用的结论：数组中右边第一个比我小的元素的位置，求解用递增栈。
这里给你留几道练习题，请你思考如何求解。
- 数组中右边第一个比我大的元素的位置
- 数组中元素左边离我最近且比我小的元素的位置
- 数组中元素左边离我最近且比我大的元素的位置
如果我们进一步归纳，会发现消除的时候，这里仍然是消除一个元素，保留一个元素。弹栈的时候，仍然是一直弹栈，直到满足某个条件为止。只是条件变成了直到元素大于栈顶元素。为了方便你理解，我把内容总结到了一张大图里：
例 4：字典序最小的 k 个数的子序列
【题目】给定一个正整数数组和 k，要求依次取出 k 个数，输出其中数组的一个子序列，需要满足：1. 长度为 k；2.字典序最小。
输入：nums = [3,5,2,6], k = 2
输出：[2,6]
解释：在所有可能的解：{[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，[2,6] 字典序最小。
所谓字典序就是，给定两个数组：x = [x1,x2,x3,x4]，y = [y1,y2,y3,y4]，如果 0 ≤ p < i，xp == yp 且 xi < yi，那么我们认为 x 的字典序小于 y。
接口：int[] findSmallSeq(int[] A, int k);
【分析】根据 “四步分析法”，我们一步一步拆解题目。
1. 模拟
首先应该拿例子来模拟一下题目所述的过程，动图如下所示：
2. 规律
通过模拟，我们发现一个特点：一旦发现更小的数时，就可以把前面已经放好的数扔掉，然后把这个最小的数放在最前面。
如果机智一点，就会发现这里与例 2 的“大鱼吃小鱼” 结果很像。区别在于消除的过程中，大鱼吃小鱼是大鱼留下来了，而这里较小的数和较大的数相遇时，是较小的数留下来了。
3. 匹配
到这里，我们已经发现了题目的特点——较小数消除掉较大数。根据例 3 总结出来的规律，此时就可以用上单调栈。并且，由于是较小的数消除掉较大的数，所以应该使用递增栈。
4. 边界
不过我们还是需要小心题目的边界。
Case 1：假设数组右边有一个最小的数，这个最小的数会把左边的数全部都消掉，然后递增栈里面就只剩下这 1 个数了。这跟题意有点不符合，题意需要的是找到 k = 2 个出来。
解决办法：不过你可以想一想，是不是可以控制一下消去的数目。当剩下的数字个数与栈中的元素刚好能凑够 k 个数时，就不能再消除了，代码如下 :
rightLeftNumber + stack.size() == k
此时，如果还要进行消除，就不能凑够 k 个数了。这样操作可以保证我们取的序列是最小的 k 个数。
Case 2：如果数组是一个升序的数组，那么此时所有的元素都会被压栈。栈中的数目有可能远远超出 k 个。
解决办法：只需要把栈中的多出来的数字弹出来即可。
【画图】假定输入为[9, 2, 4, 5, 1, 2, 3, 0], k = 3. 输出能构成的最小的序列。
Step 1. 首先将 9 加入栈中。
Step 2. 当 2 要入栈时，不满足单调栈，需要将数字 9 出栈。由于后面还有足够多的元素，可以把 9 弹栈，再将 2 入栈。
Step 3. 将 4 入栈，满足单调性。
Step 4. 再将元素 5 入栈，满足单调性。
Step 5. 将要入栈的元素 1，会弹出栈中所有元素。
Step 6. 将元素 1 入栈。
Step 7. 将元素 2 入栈，满足单调性。
Step 8. 将元素 3 入栈，满足单调性。
Step 9. 将 0 入栈时，需要将栈顶元素 3 弹出。
Step 10. 将 0 入栈，不满足单调性。这是因为，如果 0 将前面的元素再弹栈，余下的元素个数就小于 k = 3 个了。所以不能再利用单调性来弹出栈中元素了。
【代码】到这里，相信你已经可以根据思路写出代码了，代码如下（解析在注释里）：
public int[] findSmallSeq(int[] nums, int k) {int[] ans = new int[k];Stack<Integer> s = new Stack();for (int i = 0; i < nums.length; i++) {final int x = nums[i];final int left = nums.length - i;while (!s.empty() && (s.size() + left > k) && s.peek() > x) {s.pop();}s.push(x);}while (s.size() > k) {s.pop();}for (int i = k - 1; i >= 0; i--) {ans[i] = s.peek();s.pop();}return ans;}
复杂度分析：每个元素只入栈一次，出栈一次，所以时间复杂度为 O(N)，而空间复杂度为 O(N)，因为最差情况可能会把所有元素都入栈。
【小结】写完代码之后，我们需要对代码和题目做一个小结：
- 较小的数消除掉较大的数的时候，使用递增栈；
- 要注意控制剩下的元素的个数；
如果更进一步推而广之，会发现从简单栈到单调栈，层层推进的过程中，不停变化就是入栈与出栈的时机。
那么，到这里，这个题目的考点也就非常明了了：
- 递增栈
- 个数控制，我们只需要取 k 个数出来。
总结与延伸
在本讲我带你一起剖析了栈相关的知识和题目，经过我们不断地 “浇灌”，栈这棵“萌芽” 开始抽枝散叶，终于长成了一棵枝繁叶茂的“大树”。回到知识层面，我把本讲重点介绍、且需要你掌握的内容总结在一张思维导图中，如下图所示：
除了带你学习知识本身，我还介绍了题目的变形和演进，希望能够帮助你建立深度分析的能力。在学习算法与数据结构的过程中，作为 “刷题过来人”，我非常建议你加强总结和归纳 ，建立自己的学习方法论。
虽然栈很有趣，不过我们的介绍就要到这里了，我对于栈的总结和归纳只是个开头，期待你还能发现更多栈的特点和巧妙用法，并且将它们总结下来。也欢迎在评论区和我交流，期待看到你的奇思妙想。
思考题
我再给你留一道思考题：给定一个数组，数组中的元素代表木板的高度。请你求出相邻木板能剪出的最大矩形面积。
这道题会涉及一个非常重要且有用的单调栈的性质，希望你能找到它。你可以把答案写在评论区，我们一起讨论。
接下来请和我一起踏上更加奇妙的算法与数据结构的旅程。让我们继续前进。下一讲将介绍 02 | 队列：FIFO 队列与单调队列的深挖与扩展，记得按时来探险。
若有收获，就点个赞吧
0 人点赞
