始于
分类：LeetCode
Tags: [ LeetCode C++ ]
单调栈的一个例子
LeetCode 2454. 下一个更大元素 IV
这是 Biweekly 90 的题目，我后补的。之前接触过单调栈，不是很熟，这次写一篇文章简单讲一下。
原题是这样的：
给你一个下标从 0 开始的非负整数数组 nums 。对于 nums 中每一个整数，你必须找到对应元素的 第二大 整数。
如果 nums[j] 满足以下条件，那么我们称它为 nums[i] 的 第二大 整数：
j > inums[j] > nums[i]- 恰好存在 一个
k满足i < k < j且nums[k] > nums[i]。
如果不存在 nums[j] ，那么第二大整数为 -1 。
- 比方说，数组
[1, 2, 4, 3]中，1的第二大整数是4，2的第二大整数是3，3和4的第二大整数是-1。
请你返回一个整数数组 answer ，其中 answer[i]是 nums[i] 的第二大整数。
输入： nums = [2,4,0,9,6]
输出： [9,6,6,-1,-1]
在看这题之前，先要了解一下单调栈。给个单调栈的例子：给你一个数组，让你求所有数的下一个更大值，如果没有则返回 -1。比如给你一个数组 [2, 1, 2, 4, 3]，就应该返回 [4, 2, 4, -1, -1]。这类问题被叫作 next greater element。下面是 labuladong 给出的代码：
vector<int> nextGreaterElement(vector<int>& nums) {
vector<int> ans(nums.size());
stack<int> s;
for (int i = nums.size() - 1; i >= 0; i--) {
while (!s.empty() && s.top() <= nums[i]) {
s.pop();
}
ans[i] = s.empty() ? -1 : s.top();
s.push(nums[i]);
}
return ans;
}
单调栈是一个线性结构（废话），里面的元素是有序的，但是又不同于堆，单调栈中的元素是筛选的（selected）。大概的工作逻辑是：我遍历一个数组，遇到比我这个栈顶小（符合 comparer 的）的元素就往里放，这样不就能非常暴力的达到单调栈的需求了吗？
template <typename V, typename F>
requires requires (F f) {
typename std::decay_t<V>::value_type{};
{ f(typename std::decay_t<V>::value_type{}, typename std::decay_t<V>::value_type{}) };
}
void monotonic_stack(V&& v, F&& f) {
using T = typename std::decay_t<V>::value_type;
std::vector<T> stk;
for (auto&& a : v) {
if (stk.empty() || f(a, stk.back())) {
stk.push_back(a);
}
std::copy(std::begin(stk), std::end(stk), std::ostream_iterator<T>(std::cout, ", "));
std::endl(std::cout);
}
}
比如传 monotonic_stack(std::vector{2, 1, 2, 4, 3}, std::less<int>{}); 的结果是：
2,
2, 1,
2, 1,
2, 1,
2, 1,
但是这只是单调栈的行为的一半，实际上遇到比栈顶大（不符合 comparer 的）的元素要一直 pop 到可以放为止。所以修改代码：
template <typename V, typename F>
requires requires (F f) {
typename std::decay_t<V>::value_type{};
{ f(typename std::decay_t<V>::value_type{}, typename std::decay_t<V>::value_type{}) };
}
void monotonic_stack(V&& v, F&& f) {
using T = typename std::decay_t<V>::value_type;
std::vector<T> stk;
for (auto&& a : v) {
while (!stk.empty() && !f(a, stk.back())) {
stk.pop_back();
}
stk.push_back(a);
std::copy(std::begin(stk), std::end(stk), std::ostream_iterator<T>(std::cout, ", "));
std::endl(std::cout);
}
}
这次的结果是：
2,
2, 1,
2,
4,
4, 3,
将这个代码稍加改造就可以得到 next greater element 的结果了：
#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <functional>
#include <type_traits>
template <typename V, typename F>
requires requires (F f) {
typename std::decay_t<V>::value_type{};
{ f(typename std::decay_t<V>::value_type{}, typename std::decay_t<V>::value_type{}) };
}
void monotonic_stack(V&& v, F&& f) {
using T = typename std::decay_t<V>::value_type;
std::vector<T> stk;
for (auto&& a : v) {
while (!stk.empty() && !f(a, stk.back())) {
stk.pop_back();
}
std::cout << (stk.empty() ? -1 : stk.back()) << std::endl;
stk.push_back(a);
}
}
int main()
{
auto v {std::vector{2, 1, 2, 4, 3}};
std::reverse(std::begin(v), std::end(v));
monotonic_stack(v, std::less<int>{});
}
输出为：
-1
-1
4
2
4
这是结果的逆序。为什么需要倒着跑单调栈？因为我们需要的是「后面的」更大值，所以需要创建的是一个逆序遍历的「小顶堆」，这样才能保证我们需要的元素在栈中。
我们从后往前、记最后一个元素为第 0，对于第 0 个元素，有单调栈为空，第 0 个元素入栈，显然即一个单调栈；对于第 N 个元素，在开始时已经有了 [0:N) 元素构造的单调栈，接着将第 N 个元素入栈，先执行所需的 pop 操作，而后 push 自身进栈，显然这个栈构成了 [0:N] 元素的单调栈。因为单调栈的元素的序与数组中的原序相同，所以栈中的第二个元素就是第 N 个元素（栈顶）的 next greater number：比第二个元素小的更靠栈顶的元素不能提前出栈；比第二个元素大的更靠栈顶的元素不存在，因为根据单调栈的定义，如果真的存在这样一个元素，原本的第二个元素的存在矛盾；而在第 N 个元素的构造单调栈的过程中，已经排除了比它小的元素的情况。因为栈只能取栈顶，所以在第 N 个元素入栈之前，先获得需要的 next greater number 即可。
回到 LC 2454，这这题需要构造两个单调栈，用来保存两种状态的入栈元素：无后继更大元素的下标栈和有一个后继更大元素的下标栈，有两个后继更大元素的就要出栈然后更新结果数组了。
class Solution {
public:
vector<int> secondGreaterElement(vector<int>& nums) {
int n = nums.size();
vector<int> r(n, -1), s, t;
for (int i = 0; i < n; ++i) {
int k = nums[i];
while (!t.empty() && nums[t.back()] < k) {
r[t.back()] = k;
t.pop_back();
}
int j = (int) s.size() - 1;
while (j >= 0 && nums[s[j]] < k) {
--j;
}
t.insert(t.end(), s.begin() + (j + 1), s.end());
s.resize(j + 1);
s.push_back(i);
}
return r;
}
};
这里的 s 和 t 分别是提到的两个数组。注意这里的 s 和 t 中存的是遍历过的下标。每次循环开始时，首先需要判断是否有元素需要出栈：
while (!t.empty() && nums[t.back()] < k) {
r[t.back()] = k;
t.pop_back();
}
如果当前元素比 t 栈顶的元素（注意栈中存的是下标，但是后文都还简称栈中元素）还大，显然这就是 t 栈顶元素的下下一个更大元素，因为 t 中存储的就是已经经历过它们的下一个更大元素的元素。
接着需要在 s 栈中找到比当前遍历元素小的元素，因为这是一个小顶的有序栈，所以这个过程还是挺方便的。于是这些元素（j + 1 到 s.size 范围内的）都是比当前遍历元素小的元素，自然就算是经历了下一个更大的元素了，自然要把它们「移动」到 t 中。这样整个行为就完备了。
t.insert(t.end(), s.begin() + (j + 1), s.end());
s.resize(j + 1);
s.push_back(i);
这里用到了 vector::insert 的一个不是很常用的（至少我没用过？）一个 overload，将一个 range 插到位置中：
template <class InputIt>
constexpr iterator insert(const_iterator pos, InputIt first, InputIt last);
值得一提的是它还提供了一个接收 std::initializer_list<T> 的 overload：
constexpr iterator insert(const_iterator pos,
std::initializer_list<T> ilist);
这让我想到了 std::max 。
然后就是用 resize 削除 vector 的后面的部分。这个成员函数我也没有用过，以及不知道可以这么用。当然如果 s.erase(s.begin() + (j + 1), s.end()) 应该也可以？
这里还要提一嘴，这个 (j + 1) 的括号一定不能少，因为这个 j 可以等于 -1 的。
那么这些就是这题的单调栈。后面再看 labuladong 的算法的时候可能还会再见到这题，而后还会有更多的练习，这也就之后再说了。