算法专题-单调栈
算法专题-单调栈
单调栈是一种特殊的栈数据结构，其元素从栈顶到栈底遵循一定的单调性（递增或递减）。这种特性使得单调栈在处理某些特定问题时非常高效，例如寻找数组中某个元素左侧或右侧第一个比它大或小的元素。本文将详细介绍单调栈的概念、实现方法及其在算法题目中的应用。
定义
一句话解释单调栈，就是一个栈，里面的元素的大小按照他们所在栈内的位置，满足一定的单调性。
单调栈（Monotone Stack）：一种特殊的栈。在栈的「先进后出」规则基础上，要求「从 栈顶 到 栈底 的元素是单调递增（或者单调递减）」。其中满足从栈顶到栈底的元素是单调递增的栈，叫做「单调递增栈」。满足从栈顶到栈底的元素是单调递减的栈，叫做「单调递减栈」。
注意：这里定义的顺序是从「栈顶」到「栈底」。有的文章里是反过来的。本文全文以「栈顶」到「栈底」的顺序为基准来描述单调栈。
听起来有点像堆（heap）？不是的，单调栈用途不太广泛，只处理一类典型的问题，比如「下一个更大元素」，「上一个更小元素」等。本文用讲解单调队列的算法模版解决「下一个更大元素」相关问题，并且探讨处理「循环数组」的策略。至于其他的变体和经典例题，会在下一篇文章中讲解。
单调递增栈
单调递增栈：只有比栈顶元素小的元素才能直接进栈，否则需要先将栈中比当前元素小的元素出栈，再将当前元素入栈。
这样就保证了：栈中保留的都是比当前入栈元素大的值，并且从栈顶到栈底的元素值是单调递增的。
单调递增栈的入栈、出栈过程如下：
- 假设当前进栈元素为 x，如果 x 比栈顶元素小，则直接入栈。
- 否则从栈顶开始遍历栈中元素，把小于 x 或者等于 x 的元素弹出栈，直到遇到一个大于 x 的元素为止，然后再把 x 压入栈中。
下面我们以数组 [2, 7, 5, 4, 6, 3, 4, 2] 为例，模拟一下「单调递增栈」的进栈、出栈过程。具体过程如下：
最终栈中元素为 [7, 6, 4, 2]。因为从栈顶（右端）到栈底（左侧）元素的顺序为 2, 4, 6, 7，满足递增关系，所以这是一个单调递增栈。
我们以上述过程第 5 步为例，所对应的图示过程为：
单调递减栈
单调递减栈：只有比栈顶元素大的元素才能直接进栈，否则需要先将栈中比当前元素大的元素出栈，再将当前元素入栈。
这样就保证了：栈中保留的都是比当前入栈元素小的值，并且从栈顶到栈底的元素值是单调递减的。
单调递减栈的入栈、出栈过程如下：
- 假设当前进栈元素为 x，如果 x 比栈顶元素大，则直接入栈。
- 否则从栈顶开始遍历栈中元素，把大于 x 或者等于 x 的元素弹出栈，直到遇到一个小于 x 的元素为止，然后再把 x 压入栈中。
下面我们以数组 [4, 3, 2, 5, 7, 4, 6, 8] 为例，模拟一下「单调递减栈」的进栈、出栈过程。具体过程如下：
数组元素：[4, 3, 2, 5, 7, 4, 6, 8]，遍历顺序为从左到右。
最终栈中元素为 [2, 4, 6, 8]。因为从栈顶（右端）到栈底（左侧）元素的顺序为 8, 6, 4, 2，满足递减关系，所以这是一个单调递减栈。
我们以上述过程第 6 步为例，所对应的图示过程为：
单调栈适用场景
单调栈可以在时间复杂度为O ( n ) O(n)O(n)的情况下，求解出某个元素左边或者右边第一个比它大或者小的元素。
所以单调栈一般用于解决一下几种问题：
- 寻找左侧第一个比当前元素大的元素。
- 寻找左侧第一个比当前元素小的元素。
- 寻找右侧第一个比当前元素大的元素。
- 寻找右侧第一个比当前元素小的元素。
下面分别说一下这几种问题的求解方法。
寻找左侧第一个比当前元素大的元素
从左到右遍历元素，构造单调递增栈（从栈顶到栈底递增）：
- 一个元素左侧第一个比它大的元素就是将其「插入单调递增栈」时的栈顶元素。
- 如果插入时的栈为空，则说明左侧不存在比当前元素大的元素。
寻找左侧第一个比当前元素小的元素
从左到右遍历元素，构造单调递减栈（从栈顶到栈底递减）：
- 一个元素左侧第一个比它小的元素就是将其「插入单调递减栈」时的栈顶元素。
- 如果插入时的栈为空，则说明左侧不存在比当前元素小的元素。
寻找右侧第一个比当前元素大的元素
从左到右遍历元素，构造单调递增栈（从栈顶到栈底递增）：
- 一个元素右侧第一个比它大的元素就是将其「弹出单调递增栈」时即将插入的元素。
- 如果该元素没有被弹出栈，则说明右侧不存在比当前元素大的元素。
从右到左遍历元素，构造单调递增栈（从栈顶到栈底递增）：
- 一个元素右侧第一个比它大的元素就是将其「插入单调递增栈」时的栈顶元素。
- 如果插入时的栈为空，则说明右侧不存在比当前元素大的元素。
寻找右侧第一个比当前元素小的元素
从左到右遍历元素，构造单调递减栈（从栈顶到栈底递减）：
- 一个元素右侧第一个比它小的元素就是将其「弹出单调递减栈」时即将插入的元素。
- 如果该元素没有被弹出栈，则说明右侧不存在比当前元素小的元素。
从右到左遍历元素，构造单调递减栈（从栈顶到栈底递减）：
- 一个元素右侧第一个比它小的元素就是将其「插入单调递减栈」时的栈顶元素。
- 如果插入时的栈为空，则说明右侧不存在比当前元素小的元素。
上边的分类解法有点绕口，可以简单记为以下条规则：
无论哪种题型，都建议从左到右遍历元素。
- 查找 「比当前元素大的元素」 就用 单调递增栈，查找 「比当前元素小的元素」 就用 单调递减栈。
- 从 「左侧」 查找就看 「插入栈」 时的栈顶元素，从 「右侧」 查找就看 「弹出栈」 时即将插入的元素。
算法题
下一个更大的元素
输入一个数组 nums，请你返回一个等长的结果数组，结果数组中对应索引存储着下一个更大元素，如果没有更大的元素，就存 -1。函数签名如下：
vector<int> calculateGreaterElement(vector<int>& nums);
比如说，输入一个数组 nums = [2,1,2,4,3]，你返回数组 [4,2,4,-1,-1]。因为第一个 2 后面比 2 大的数是 4; 1 后面比 1 大的数是 2；第二个 2 后面比 2 大的数是 4; 4 后面没有比 4 大的数，填 -1；3 后面没有比 3 大的数，填 -1。
这道题的暴力解法很好想到，就是对每个元素后面都进行扫描，找到第一个更大的元素就行了。但是暴力解法的时间复杂度是 O(n^2)O(n^2)。
这个问题可以这样抽象思考：把数组的元素想象成并列站立的人，元素大小想象成人的身高。这些人面对你站成一列，如何求元素「2」的下一个更大元素呢？很简单，如果能够看到元素「2」，那么他后面可见的第一个人就是「2」的下一个更大元素，因为比「2」小的元素身高不够，都被「2」挡住了，第一个露出来的就是答案。
vector<int> calculateGreaterElement(vector<int>& nums) {
int n = nums.size();
// 存放答案的数组
vector<int> res(n);
stack<int> s;
// 倒着往栈里放
for (int i = n - 1; i >= 0; i--) {
// 判定个子高矮
while (!s.empty() && s.top() <= nums[i]) {
// 矮个起开，反正也被挡着了。。。
s.pop();
}
// nums[i] 身后的更大元素
res[i] = s.empty() ? -1 : s.top();
s.push(nums[i]);
}
return res;
}
84. 柱状图中最大的矩形
LeetCode84
分析
单调栈的时间复杂度是多少？直接计算十分困难，但是我们可以发现：
每一个位置只会入栈一次（在枚举到它时），并且最多出栈一次。
因此当我们从左向右/总右向左遍历数组时，对栈的操作的次数就为 O(N)。所以单调栈的总时间复杂度为 O(N)。
/*
首先从左往右对数组进行遍历，借助单调栈求出了每根柱子的左边界，
随后从右往左对数组进行遍历，借助单调栈求出了每根柱子的右边界
*/
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
vector<int> left(n), right(n);
// 从左往右，构建单调递减栈，寻找左侧第一个比当前元素小的元素
stack<int> mono_stack;
for (int i = 0; i < n; ++i) {
while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
mono_stack.pop();
}
left[i] = (mono_stack.empty() ? -1 : mono_stack.top());
mono_stack.push(i);
}
// 从右往左，构建单调递减栈，寻找右侧第一个比当前元素小的元素
mono_stack = stack<int>();
for (int i = n - 1; i >= 0; --i) {
while (!mono_stack.empty() && heights[mono_stack.top()] >= heights[i]) {
mono_stack.pop();
}
right[i] = (mono_stack.empty() ? n : mono_stack.top());
mono_stack.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
};
85 最大矩形
Leetcode
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
将输入拆分成一系列的柱状图。为了计算矩形的最大面积，我们只需要计算每个柱状图中的最大面积，并返回全局最大值。
首先计算出矩阵的每个元素的左边连续 1 的数量，使用二维数组 left 记录，其中 left[i][j] 为矩阵第 i 行第 j 列元素的左边连续 1 的数量。
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;
/*
up[i]:每一列中，行i上方最近的一个比left[i][j]小的行号，如果不存在则为-1；
down[i]:每一列中，行i下方最近的一个比right[i][j]小的行号，如果不存在则为m；
*/
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
int m = matrix.size();
if (m == 0) {
return 0;
}
int n = matrix[0].size();
vector<vector<int>> left(m, vector<int>(n, 0));
// left[i][j]表示第i行，第j个元素左边相邻的left值加1：每个位置左边连续的'1'的个数（包括自己）
// 每一列可以看做是一个柱状图（84题中的场景），每个位置高度为left[i][j]
// 然后对每一列求最大矩形面积即可。
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '1') {
left[i][j] = (j == 0 ? 0: left[i][j - 1]) + 1;
}
}
}
int ret = 0;
for (int j = 0; j < n; j++) { // 对于每一列，使用基于柱状图的方法
vector<int> up(m, 0), down(m, 0);
// 单调递减栈；up[i]: up[i]为当前下标i左边第一个比它小的下标，如果不存在则为-1
stack<int> stk;
for (int i = 0; i < m; i++) {
while (!stk.empty() && left[stk.top()][j] >= left[i][j]) {
stk.pop();
}
up[i] = stk.empty() ? -1 : stk.top();
stk.push(i);
}
// 单调递减栈;down[i]:当前下标i右边第一个比它小的下标，如果不存在则为m
stk = stack<int>();
for (int i = m - 1; i >= 0; i--) {
while (!stk.empty() && left[stk.top()][j] >= left[i][j]) {
stk.pop();
}
down[i] = stk.empty() ? m : stk.top();
stk.push(i);
}
for (int i = 0; i < m; i++) {
int height = down[i] - up[i] - 1;
int area = height * left[i][j];
ret = max(ret, area);
}
}
return ret;
}
};