面试必考的基础数据结构梳理（1）

栈属于基础数据结构之一，基础到仅用「后进先出」这四个字即可完整概括其核心特征。然而，基础并不代表着简单，「后进先出」的背后反而隐藏着多样的变化与极其广泛的应用。

在本篇文章中，我们将针对在基础栈上稍加改动所形成的「单调栈」算法进行详解。该算法与「单调队列」组成了算法题中最常考察的线性数据结构，属于面试中必知必会的算法知识。

栈

首先我们来回忆一下「栈」。「栈」是一种「后进先出」的线性数据结构，其只有一端（栈顶）可以任意进出元素，而另一端（栈底）则无法进行任何操作。

如下图所示，3 1 4 5 2 7 依次入栈又依次出栈，其过程仅有栈顶在不断移动，其结果则满足「后进先出」的要求。

单调栈

回忆完「栈」后，我们来进行「单调栈」的讲解。

什么是「单调栈」？顾名思义，「单调栈」就是栈内元素满足单调性的栈结构。此处的单调性分为单调递增与单调递减，为了便于描述，接下来以「单调递增栈」为例进行讲解。

「单调递增栈」就是栈内元素满足单调递增，假设当前元素为 x，若栈顶元素 ≤ x，则将 x 入栈，否则不断弹出栈顶元素，直至栈顶元素 ≤ x。

我们仍以 3 1 4 5 2 7 为例，其「单调递增栈」具体过程如下图所示。不难发现，入栈结束后，栈中仅保留了 1 2 7，其中 3 由于比 1 大被弹出，而 4 与 5 则由于比 2 大被弹出。

请大家仔细观看上述示例，理解清楚「单调递增栈」的具体操作后再往下看。

理解完上述示例后，我相信大家都会有一个疑问，即「在栈中维护单调性究竟有什么用呢」？

要回答这个问题，我们首先来观察一下上述示例中 2 为当前元素时的状态，如下图所示。

在该状态中，栈顶元素为 5，而当前元素为 2，由于 5 比 2 大，即此时若将 2 放入栈内，则不满足单调递增，因此需要将 5 弹出栈。这时请大家思考，2 和 5 之间是否有什么更深层的关系，所以才导致了 5 最终被 2 弹出？

仔细观察原始序列 3 1 4 5 2 7，我们可以发现 2 是 5 右边第一个比它小的数。基于这个发现，我们再次回顾「栈顶元素被弹出，当且仅当栈顶元素 > 当前元素」这一条件，因此我们可以得知对于单调递增栈，若栈顶元素被弹出，则当前元素为其右边第一个比它小的数。

2 弹出 5 后，栈顶变为 4，此时 4 仍比 2 大，因此 4 也被弹出，这时可确定 2 是 4 右边第一个比它小的数。

4 被弹出后，栈顶变为 1，1 ≤ 2，因此 2 被放入栈，此时栈内状态如下图所示。

按照刚才的思路，我们继续思考为何最终状态下 2 的左边是 1，这两个数之间又有何关联？

继续观察原始序列 3 1 4 5 2 7，可以发现 1 是 2 左边第一个小于等于它的数，稍加思考后，我们可以得知当一个数字被放入单调递增栈时，其栈内左边的数是它在原始序列中，左边第一个小于等于它的数。

至此我们可以解答最开始的疑问，单调栈的根本作用在于求得「每一个数字在原始序列中左 / 右边第一个大于 / 小于它自身的数字」，并且由于每一个数字只会入栈一次且最多出栈一次，因此总的时间复杂度为 O(n)。

另外需要注意，一次「单调递增栈」的过程，可以求得每个数字左边第一个小于等于它的数，以及右边第一个小于它的数，此处需注意「小于等于」和「小于」的区别。除此之外，「单调递减栈」将上述的「小于」改为「大于」即可成立。

接下来我们将在「习题练习」部分对该算法的具体应用与代码编写做进一步的讲解。

习题练习

503. 下一个更大元素 II

题目描述

给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

示例

输入: [1,2,1]输出: [2,-1,2]解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数；第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

注意

输入数组的长度不会超过 10000。

解题思路

该题有两个考察点，一个是「循环数组」，另一个是「每个数字之后第一个比它大的数」。对于「循环数组」，常见的操作是将数组扩充一倍，即原数组为 [1 2 3]，扩充一倍后为 [1 2 3 1 2 3]。扩充后的数组包含了循环数组中所有可能出现的序列，因此「扩充一倍」操作可以将循环数组转变为普通数组。

解决完「循环数组」后，第二个考察点便转变为「每个数字右边第一个比它大的数」，因此我们用「单调递减栈」来解决。

用数组模拟栈，用一个变量来代表栈顶位置，从左至右遍历数组，若栈为空或当前数字小于等于栈顶数字，则将当前数字入栈。否则不断弹出栈顶元素，直至条件满足。

在弹出「栈顶元素」时，便可确定「栈顶元素」右边第一个比它大的数，即「当前元素」。若栈内元素始终未被弹出，则其右边没有数比它更大。

至此本题得以解决，具体细节可参考下述代码。

代码实现

classSolution {public:vector<int> nextGreaterElements(vector<int>& nums) {int len = nums.size(), top = -1;vector<int> ans(len, -1), stk(2*len); nums.resize(2*len);for (int i = len; i < 2*len; i++) nums[i] = nums[i-len];for (int i = 0; i < 2*len; i++) {while(top >= 0 && nums[i] > nums[stk[top]]) {if (stk[top] < len) ans[stk[top]] = nums[i]; top--; } stk[++top] = i; }return ans; }};

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例

输入: [2,1,5,6,2,3]输出: 10

解题思路

矩形面积仅跟矩形的高和宽有关，因此我们观察题目中第二张图所覆盖的矩形，思考其高和宽分别有什么特点？

首先是矩形的高度，仔细观察后不难发现，最大面积矩形的高度一定等于某根柱子的高度，因此我们可以枚举柱子，令其为矩形的高度。

确定了作为矩形高度的柱子后，我们继续思考以该柱子为高所延伸的最大宽度有何特点？

假设当前柱子高度为 x，右边柱子的高度为 y，则当且仅当 x ≤ y，矩形宽度才能向右延伸。

由此我们可以发现以某根柱子为高的矩形，其宽度由该根柱子左 / 右第一根比它矮的柱子的位置所决定。

具体来说，假设当前柱子高度为 x，左边第一根比它矮的柱子位置为 p1，右边第一根比它矮的柱子位置为 p2。若 p1 不存在则令其为 0，若 p2 不存在，则令其为 n + 1，此时以当前柱子为高的最大矩形面积为

。

因此该问题转换为「如何快速求取每根柱子左 / 右边第一根比它矮的柱子的位置」，由此自然地想到使用单调栈来解决。

回顾之前「单调递增栈」的过程，使用一次「单调递增栈」，我们可以在 O(n) 的时间复杂度内求得每个数字左边第一个小于等于它的位置，即 h1，以及右边第一个比小于它的位置，即 h2。

此处需要注意「小于等于」和「小于」的区别。例如数组 [1 3 3 3 4]，对于第二个 3 来说，

，但

，即仅使用一次「单调栈递增栈」无法求得每个数字左边第一个小于它的位置。

这时候我们有两种做法，第一种是从右往左使用「单调递增栈」，即可求得每个数字左边第一个小于它的位置。

而第二种方法则是仅用一次「单调递增栈」进行求取，最终答案为

。虽然对于每个 x 来说，我们无法求得正确的左边界，即

，但对最终的答案没有任何影响。

这是因为在最大面积矩形中，如果有若干个柱子的高度都等于矩形的高度，那么最左侧的那根柱子是可以求出正确的左边界的，因为其左边不再有与其高度相同的柱子。

仍以数组 [1 3 3 3 4] 举例，最大面积矩形的高度为 3，宽度为 4，虽然第二个 3 所求得的左边界是不准确的，但第一个 3 仍可以求得准确的左边界，使得最终答案

不会发生变化。

这一部分需要大家再仔细思考一下，具体细节则见下述代码。

最后提醒一下，如果大家无法理解上述思路的话，建议直接抛开题解，自行根据「单调栈的作用」为线索来自行思考，思考遇到瓶颈后再来查看题解，这样的学习过程对思维能力的提升会有更大的帮助。

代码实现

classSolution {public:intlargestRectangleArea(vector<int>& heights){int len = heights.size(), top = -1, ans = 0;vector<int> l(len, 0), r(len, len-1), stk(len);for (int i = 0; i < len; i++) {while (top >= 0 && heights[i] < heights[stk[top]]) { r[stk[top]] = i-1; top--; }if (top >= 0) l[i] = stk[top]+1; stk[++top] = i; }for (int i = 0; i < len; i++) ans = max(ans, heights[i]*(r[i]-l[i]+1));return ans; }};

85. 最大矩形

题目描述

给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

示例 1

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]输出：6解释：最大矩形如上图所示。

示例 2

输入：matrix = []输出：0

示例 3

输入：matrix = [["0"]]输出：0

示例 4

输入：matrix = [["1"]]输出：1

示例 5

输入：matrix = [["0","0"]]输出：0

提示

1. matrix[i][j] 为 '0' 或 '1'2. cols == matrix[0].length3. 0 <=row, cols <= 2004.matrix[i][j] 为 '0' 或 '1'

解题思路

上一题是求「柱形图」中的最大矩形，而本题是求「01 矩阵」中只包含 1 的最大矩形。

做算法题时一定要考虑题目之间的关联，思考题目之间是否能够进行转换，这样思考的次数多了，做的题多了，慢慢地就会发现很多题其实都是在某个题上稍加变换所得来的。

回到本题，思考「01 矩阵」与柱形图之间的关系。

观察示例 1 的图片，我们将第三行作为最大矩形的底部，则可以得到如下柱形图，而该柱形图中的最大矩形刚好为全图的最大矩形。

基于上述观察，我们可以将「01 矩阵」转换为「柱形图」，即枚举每一行作为最大矩形所在的底边，该行中每个 1 向上延伸的高度即为柱子的高度，对该行所形成的「柱形图」执行一遍「单调递增栈」，即可求得该行的答案。所有行答案的最大值即为本题最终答案。

由此我们仅需解决最后一个问题，即「如何快速求取每行柱子的高度」。此处我们可以使用递推的方式来解决，假设当前位置为 0，则柱子高度为 0；假设当前位置为 1，则柱子高度等于上一行该位置的柱子高度加一。

至此我们便成功地将「01 矩阵」转换为了「柱形图」，该问题得以解决，具体细节见下述代码。

代码实现

classSolution {public:intmaximalRectangle(vector<vector<char>>& matrix) {if (matrix.size() == 0) return0;int row = matrix.size(), col = matrix[0].size(), ans = 0;vector<int> base(col, 0);for (int i = 0; i < row; i++) {int top = -1;vector<int> l(col, 0), r(col, col-1), stk(col);for (int j = 0; j < col; j++) {if (matrix[i][j] == '0') base[j] = 0;elsebase[j] += 1;while (top >= 0 && base[j] < base[stk[top]]) { r[stk[top]] = j-1; top--; }if (top >= 0) l[j] = stk[top]+1; stk[++top] = j; }for (int j = 0; j < col; j++) ans = max(ans, base[j]*(r[j]-l[j]+1)); }return ans; }};

总结

本篇文章主要讲解了「单调栈」算法，其中对于「单调递增栈」，我们在一遍扫描中求得每个数字左边第一个小于等于它的数，以及右边第一个小于它的数。另外，若想求得每个数字左边第一个小于它的数，则需要从右往左再扫描一遍数组。而对于「单调递减栈」，只需将上述的「小于」改为「大于」即可。

这里提醒一下大家，不要去尝试记忆上述的结论，而应该去深刻理解「单调栈」本质上就是「在栈内维护元素单调性」，而其作用则为「O(n) 时间复杂度内求取每个数字在整个数组中左 / 右第一个大于 / 小于它的数」。算法重点在于理解，而不是记忆，当遇到与「单调栈」有关的题目时，再去现推上述的结论，这样才算真正地掌握了这个算法。

BY /

本文作者：Gene_Liu

编辑&版式：霍霍