算法系列：单调栈
source link: https://muyuuuu.github.io/2022/05/20/monotonic-stack/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
单调栈属于栈的具体应用，而非栈这种数据结构的简单使用。此类问题一般用于求解以下场景：序列中某个元素的下一个最大元素，和下一个最大元素的跨度等。以序列 [2,1,3,4] 为例，1 的下一个最大元素就是 3，而不是 4。对于这种问题都可以用单调栈求解。
为什么用单调栈
同样以 [2,1,3,4] 为例，假设此时我们有一个容器，输入一个数，容器顶部的元素是下一个最大的数。对于 1 而言，后面的最大元素是 3，因此可以得到一个结论：3 比 1 先进入容器，更通用一些：如果判断下一个最大元素，序列就要倒序进入容器，如果判断上一个最大元素，序列就要顺序进入容器。
由于 1 比 2 先进入容器，但 2 的下一个最大元素是 3 而不是 1，那么就需要在容器中进行一些操作来删除 1。即 1 比 2 早进入容器，却要先从容器种出来，那么有什么容器是后入先出的呢？当然是栈。这也就是单调栈的由来。我们总结一下：
- 如果是求下一个最大元素，就需要倒序遍历序列，否则正序遍历；
- 判断输入的元素和栈顶元素的关系，如果是求最大元素，那么就需要弹出栈顶所有的小元素；
不过还有一些小细节，这个就来看具体的题目了。
下一个最大/小元素
496. 下一个更大元素 I
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的下一个更大元素 。示例：
输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
根据前面的结论，写出程序并分析：
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
stack<int> stk;
unordered_map<int, int> m1;
vector<int> res(10005, -1);
// 求下一个最大元素，因此要倒序进入
for (int i = nums2.size() - 1; i >= 0; i--) {
// 弹出栈顶的小元素
while (!stk.empty() && nums2[i] >= stk.top()) {
stk.pop();
}
// 栈为空，说明没有比当前元素更大的，只能 -1
// 否则栈顶比输入大
res[nums2[i]] = stk.empty() ? -1 : stk.top();
// 并把当前元素放入栈中，用去后面序列元素的判断
stk.push(nums2[i]);
}
vector<int> ans;
for (auto i : nums1) {
ans.push_back(res[i]);
}
return ans;
}
};
739. 每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指在第 i 天之后，才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。示例：
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
和上一题不一样的是，这个题不在求下一个最大温度了，而是下一个最大温度的索引。因此压入栈中的是索引而不是温度，索引之间的差，就是相差的天数。在判断输入元素和栈顶元素的大小关系时，根据索引访问温度即可。
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
stack<int> stk;
vector<int> res(n, 0);
// 倒序输入
for (int i = n - 1; i >= 0; i--) {
// 抛弃掉温度低的，索引访问温度
while (!stk.empty() && temperatures[i] >= temperatures[stk.top()]) {
stk.pop();
}
// 如果今天温度不是最高的，那么索引的差距就是间隔的天数
res[i] = stk.empty() ? 0 : stk.top() - i;
// 把今天放进去
stk.push(i);
}
return res;
}
};
901. 股票价格跨度
编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。
输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。
注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。
这个题问的是：序列中小于等于当前元素，因此需要正序输入，确切来说，只能正序输入。此外，next() 方法会不断的调用，如果每次调用都通过输入来重新构建栈，就会超时。因此，我们把单调栈的核心算法封装进 next() 方法即可，且由于求的是时间跨度，因此压入栈中的是索引。个人认为，能独立把这个题写出来，单调栈就可以了。
class StockSpanner {
public:
vector<int> arr;
int n = 0;
stack<int> stk;
vector<int> tmp;
StockSpanner() {
}
int next(int price) {
// 序列元素
arr.push_back(price);
int res = build(price);
return res;
}
int build(int price) {
int a;
// 保留大栈顶，如 100 60 80 则保留为 100 80
while (!stk.empty() && price >= arr[stk.top()]) {
stk.pop();
}
// 第一天，一定为 1
if (n == 0)
a = 1;
// 否则，如果栈空了，说明前几天都比今天低，就返回天数。否则就求时间跨度
else
a = stk.empty() ? n + 1 : n - stk.top();
// 把今天压入，这里先 +1 或先压入都可以，细节自行处理
stk.push(n);
n += 1;
return a;
}
};
/**
* Your StockSpanner object will be instantiated and called as such:
* StockSpanner* obj = new StockSpanner();
* int param_1 = obj->next(price);
*/
最大跨度问题
除了可以求解下一个最大元素外，单调栈还能求满足某一条件的最大跨度。
962. 最大宽度坡
给定一个整数数组 A，坡是元组 (i, j)，其中 i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。找出 A 中的坡的最大宽度，如果不存在，返回 0 。
示例 1：
输入：[6,0,8,2,1,5]
输出：4
解释：
最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5.
是不是觉得毫无头绪，我刚开始也是这么想的，后来直到看了一个不错的题解。暴力破解能得到答案，但显然会超时，单调栈是如何应用到求最大跨度问题中呢？
首先来一点点的分析，由于要求解最大跨度，因此存储的肯定为索引。在者，对于 [9,8,1,0,1,9,4,0,4,1] 而言的最大跨度，我们希望在左边找很小的值，在右边找比左边大的值。并且有两个 0，显然第一个 0 能贡献的跨度更大。因此，基于以上两点，我们可以使用栈来存储单调递减序列的而索引，即：[9,8,1,0]，对应的索引是 [0,1,2,3]。如此，满足了找左侧很小值的目标，也满足了不考虑后面的 0。
之后，我们只要倒序遍历序列，依次和栈顶元素比较大小，如果大于，那么记录跨度并弹栈。随着弹栈的进行，索引会越来越小，也容易求到更大的跨度。具体理解一下：
输入：[9,8,1,0,1,9,4,0,4,1]
单调递减元素:[9,8,1,0], 对应下标:[0,1,2,3], 严格单调递减栈s:[0,1,2,3]
j=9, nums[j]=1 > nums[s.top()]=nums[3]=0, pos=s.top()=3, pop出3, res=max(res, j-pos)=(0, 9-3)=6
nums[j]=1 = nums[s.top()]=nums[2]=1, pos=s.top()=2, pop出2, res=max(res, j-pos)=(6, 9-2)=7
nums[j]=1 < nums[s.top()]=nums[1]=8, 遍历下一个j
j=8, nums[j]=4 < nums[s.top()]=nums[1]=8, 遍历下一个j
...
...
...
不难写出程序：
class Solution {
public:
int maxWidthRamp(vector<int>& nums) {
stack<int> stk;
int n = nums.size();
for (int i = 0; i < n; i++) {
if (stk.empty() || nums[stk.top()] > nums[i]) {
stk.push(i);
}
}
int res = -1;
for (int j = n - 1; j >= 0; j--) {
while (stk.size() && nums[j] >= nums[stk.top()]) {
res = max(res, j - stk.top());
stk.pop();
}
}
return res;
}
};
前缀和之后：https://leetcode.cn/problems/longest-well-performing-interval/
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK