单调栈的最基本四类问题
单调栈
单调栈可以处理四类问题:左边第一个比其小的值,左边第一个比其大的值,右边第一个比其小的值,右边第一个比其大的值
左边第一个比其小的值
考虑以下序列:1 2 3 4 5 6
,显然每个值左边第一个比其小的值的序列是:-1 1 2 3 4 5
如果是这样:1 2 3 5 7 6
,对于 6
来说,左边第一个比其小的值是 5
,对于 6
之后值来说左边第一个小的值不可能是 7
,这是因为 7
在 6
的左边,肯定会先访问到 6
,再访问到其左边的数。如果 x
比 6
小,必然比 7
小,所以我们可以直接把 7
去掉。这样就可以构成一个单调递增的序列
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int stk[N]; int tail; int n;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
while (tail && stk[tail] >= x) tail--;
if (tail) cout << stk[tail] << " ";
else cout << "-1 ";
stk[++tail] = x;
}
return 0;
}
左边第一个比其大的值
同理,对于序列 5 4 3 2 1
,左边第一个比其大的值的序列是:-1 5 4 3 2
。
对于序列 5 3 2 1 4
,左边第一个比其大的值的序列是:-1 5 3 2 5
。
对于后续的值 x
如果左边第一个比其大的值是 4
,则输出 4
如果左边第一比其大的值不是 4
,那么必然不可能是 3 2 1
,所以我们可以把这三个值去掉,以减少比较次数
这是一个单调递减的序列
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int stk[N];
int tail;
int n;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
while (tail && stk[tail] <= x) tail--; //只需要这里改变
if (tail) cout << stk[tail] << " ";
else cout << "-1 ";
stk[++tail] = x;
}
return 0;
}
右边第一个比其小的值
这里有一个小 tip,我们只需要从右边开始枚举要数组中数,就可以将其转化为左边第一个比其小的值
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int stk[N];
int arr[N];
int tail;
int n;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> arr[i];
for (int i = n; i >= 1; i--) {
int x = arr[i];
while (tail && stk[tail] >= x) tail--;
if (tail) arr[i] = stk[tail];
else arr[i] = -1;
stk[++tail] = x;
}
for (int i = 1; i <= n; i++) {
cout << arr[i] << " ";
}
return 0;
}
右边第一个比其大的值
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int stk[N];
int arr[N];
int tail;
int n;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> arr[i];
for (int i = n; i >= 1; i--) {
int x = arr[i];
while (tail && stk[tail] <= x) tail--; //只需要这里更改
if (tail) arr[i] = stk[tail];
else arr[i] = -1;
stk[++tail] = x;
}
for (int i = 1; i <= n; i++) {
cout << arr[i] << " ";
}
return 0;
}