1.单调栈的定义

单调栈是一种特殊的栈,特殊之处在于栈内的元素都保持一个单调性,可能为单调递增,也可能为单调递减。


2.单调栈的意义

能用来维护一个单调序列,可以解决某些区间最值问题,一般题目中会含有最高、最低等单调性词汇,以及最近等词汇。

对于一道题目而言,我们需要对于条件,性质两处地方动手,来思考算法或者数据结构的突破口。


3.例题一:仰视奶牛

**例题传送门:**https://www.acwing.com/problem/content/602/

**题意:**这道题目大致意思是:每一头奶牛往右看,找到离自己最近,而且比自己身高高的牛,如果没有比自己高的牛,那么输出0即可.也就是无解判断。

算法分析
首先我们知道程序=数据结构+算法,这道题目算法,我们除了暴力+模拟,实在想不到任何解题思路.可能是我太蠢了

所以我们考虑如何通过数据结构来优化这道题目.

数据结构
对于一道题目而言,我们需要对于条件,性质两处地方动手,来思考算法或者数据结构的突破口,显然这道题目数据结构的确定,同样离不开这条不定的定律.

对于这道题目而言,我们主要是分析条件,因为我们发现这道题目所有的奶牛,都在找离着自己最近的奶牛,那么我们不得不思考,是不是要用到后进先出的栈

既然现在我们已经确定,数据结构大致为栈,那么现在我们就需要分析性质了。

分析性质
这道题目,最有用的性质,就是离自己最近,而且比自己身高高.

离自己最近:这个性质其实就是我们所谓的栈的必备性质.
身高高:看到这种类型的词汇,一定要第一时间反应,这道题目是不是拥有单调性.
经过上面的讨论,我们大致可以确定,这道题目的确拥有单调性,那么想让我们的数据结构栈,就进化成为了单调栈.

算法整合
我们可以一步步读入奶牛,对于每一头奶牛而言,判断这一头奶牛可以成为哪些奶牛的仰视对象.
于是,我们可以将当前奶牛,不断地和栈顶奶牛比较,如果说它身高大于栈顶奶牛,那么栈顶奶牛的仰视对象一定是当前奶牛,然后将栈顶奶牛出栈,进行下一次比较,直到栈为空或者栈顶奶牛身高高于它.最后再将我们当前奶牛的身高入栈.

之所以仰视对象是当前奶牛,因为它是离栈顶奶牛最近的奶牛,而且满足身高大于它.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 10;
int a[N], s[N];

int main()
{
int n;
cin >> n;
for(int i = 0; i < n; ++i) cin >> a[i];
stack<int> st;
for(int i = 0; i < n; ++i) {
while(st.size() && a[i] > a[st.top()]) {
s[st.top()] = i + 1;
st.pop();
}
st.push(i);
}
for(int i = 0; i < n - 1; ++i) cout << s[i] << endl;
cout << s[n - 1];
return 0;
}

例题2:发射站

**例题传送门:**https://www.acwing.com/problem/content/description/601/

题意分析
NN 个能量发射站排成一行,每个发射站ii 都有不相同的高度HiH_i,并能向两边同时发射能量值为ViV_i 的能量,并且发出的能量只被两边最近的且比它高的发射站接收。然后要我们求出这个最大的接受能量值是多少.

思路分析
首先我们知道程序=数据结构+算法,这道题目算法,我们除了暴力+模拟,实在想不到任何解题思路.可能是我太蠢了

所以我们考虑如何通过数据结构来优化这道题目.

数据结构
既然现在我们已经想到了数据结构来优化算法,那么现在当前最大的问题.无非就是如何利用这个我们学过数据结构来优化这道题目.

我们发现这道题目,所有的数字都满足一个非常重要的性质,那就是发出的能量只被两边最近的且比它高的发射站,我们从中间,不但会发现这道题目的条件,还会发现这道题目出题人,偷偷告诉我们的性质.那就是两边最近且比他高.

性质分析
两边最近: 显然,是一个条件&性质,而且这里面最为重要的性质核心,就是最近这个两个字.

看到这里,我们就得让神经系统中的神经元,条件反射地想到,是不是需要后进后出的数据结构栈

比他高: 这就是这道题目的第二大精髓思想,单调性,我们通过这道题目的这句话,可以敏锐地察觉到,这道题目需要使用具有单调性质的单调栈.

算法步骤
这道题目既然是需要使用具有非常秀的单调栈,那么我们到底如何使用呢?

那么此时我们就需要根据条件,来确定单调栈,插入栈顶的条件.

因为对于一个发射站而言,它可以接收到的能量,就是一组单调递减的高度序列的能量.这里我们需要画图解决问题.

综上所述,我们可以开一个单调递减的栈,统计所有高度单调递减的发射站.

  1. 如果当前这个数字破坏了单调递减,那么它会挡掉比它矮的所有发射站.
    然后将所有比它能量小的发射站,统统吸取.然后将这些发射站出栈,自己入栈.
  2. 如果当前发射站,满足单调递减的话,那么栈顶所属的发射站,吸取它的能量.同样自己也需要入栈

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e6 + 10;
int a[N], b[N], s[N];

int main()
{
int n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%d %d", a + i, b + i);
stack<pii> st;
st.push({a[1], 1});
for(int i = 2; i <= n; ++i) {
while(st.size() && a[i] > st.top().first) {
s[i] += b[st.top().second];
st.pop();
}
if(st.size()) s[st.top().second] += b[i];
st.push({a[i], i});
}
cout << *max_element(s + 1, s + n + 1) << endl;
return 0;
}