详解单调栈算法

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

前言 嘿！彩蛋！感觉有帮助就三连呗！

如果你对这篇文章可感兴趣，可以点击「【访客必读 – 指引页】一文囊括主页内所有高质量博客」，查看完整博客分类与对应链接。

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

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

栈

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

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

单调栈

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

习题练习

503. 下一个更大元素 II

题目描述

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

示例

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

注意

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

解题思路

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

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

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

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

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

代码实现

class Solution { 
   
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\le y$，矩形宽度才能向右延伸。

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

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

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

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

此处需要注意「小于等于」和「小于」的区别。例如数组 $[13334]$，对于第二个 $3$ 来说，$h_2=p_2=5$，但 $h_1=2,p_1=1$，即仅使用一次「单调栈递增栈」无法求得每个数字左边第一个小于它的位置。

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

而第二种方法则是仅用一次「单调递增栈」进行求取，最终答案为 $\underset{x}{\max }x\cdot (h_2-h_1-1)$。虽然对于每个 $x$ 来说，我们无法求得正确的左边界，即 $h_1\ne p_1$，但对最终的答案没有任何影响。

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

仍以数组 $[13334]$ 举例，最大面积矩形的高度为 $3$，宽度为 $4$，虽然第二个 $3$ 所求得的左边界是不准确的，但第一个 $3$ 仍可以求得准确的左边界，使得最终答案 $\underset{x}{\max }x\cdot (h_2-h_1-1)$ 不会发生变化。

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

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

代码实现

class Solution { 
   
public:
    int largestRectangleArea(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].length
3. 0 <= row, cols <= 200
4. matrix[i][j] 为 '0' 或 '1'

解题思路

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

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

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

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

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

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

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

代码实现

class Solution { 
   
public:
    int maximalRectangle(vector<vector<char>>& matrix) { 
   
        if (matrix.size() == 0) return 0;
        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;
                else base[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)$ 时间复杂度内求取每个数字在整个数组中左 / 右第一个大于 / 小于它的数」。算法重点在于理解，而不是记忆，当遇到与「单调栈」有关的题目时，再去现推上述的结论，这样才算真正地掌握了这个算法。

最后，希望大家在日后刷题时能及时想起该算法，祝大家刷题愉快！