帮助群友♂♂(AC)，就是帮助自己

单调栈

  • 单调递增栈：单调递增栈就是从栈底到栈顶数据是从小到大（一般）
  • 单调递减栈：单调递减栈就是从栈底到栈顶数据是从大到小
    • （我们只会用到单调栈的一端）

E.g: 单调递增栈加入数据：：：堆栈实现（栈顶为最大值）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
stack<int> st;

//栈顶为最大值
void _add(const int& x) {
	if (st.empty() || st.top() > x){
		st.push(x);
	}
	else{
		stack<int> tmp;
		while (!st.empty() && st.top() < x) {
			tmp.push(st.top()); st.pop();
		}
		st.push(x);
		
		while (!tmp.empty()) {
			st.push(tmp.top()); tmp.pop();
		}
	}
}

E.g: 单调递增栈加入数据：：：动态数组实现（(๑•̀ㅂ•́)و✧）用数组实现的真的还是单调栈吗

可恶！已经完全不是堆栈的样子了

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> v;

//数组最后一项为最大值
void _add(const int& x) {
    //找小于等于
	v.insert(lower_bound(v.begin(), v.end(), x, greater<>()), x);
}

//数组第一项为最大值
void _add(const int& x) {
    //找大于等于
	v.insert(lower_bound(v.begin(), v.end(), x), x);
}

其实堆栈没必要一定是堆栈**(๑•̀ㅂ•́)و✧**

然后对于洛谷的这一题 [COI2007] Patrik 音乐会的等待

题目描述

$n$ 个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。

队列中任意两个人 $a$ 和 $b$，如果他们是相邻或他们之间没有人比 $a$ 或 $b$ 高，那么他们是可以互相看得见的。

写一个程序计算出有多少对人可以互相看见。

输入格式

输入的第一行包含一个整数 $n$，表示队伍中共有 $n$ 个人。

接下来的 $n$ 行中，每行包含一个整数，表示人的高度，以毫微米(等于 $10^{-9}$ 米)为单位，这些高度分别表示队伍中人的身高。

输出格式

输出仅有一行，包含一个数 $s$，表示队伍中共有 $s$ 对人可以互相看见。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
7 
2 
4 
1 
2 
2 
5 
1

样例输出 #1

1
10

提示

数据规模与约定

对于全部的测试点，保证 $1\le$ 每个人的高度 $< 2^{31}$，$1 \le n \le 5\times 10^5$。

完全适合用单调栈(的概念)去做

上代码解释

注：这不是AC代码，它没有对大数据的情况进行处理，会卡TLE(代码运行超时)

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
//请牢记，这是一个  单调递减栈
//下方的ac样例也是  单调递减栈
stack<int> st;
int ans = 0;

void _add(const int& x) {
	int lap = 1;
    
    //栈非空 新值大于栈顶值（不符合我们单调递减栈的要求）
    
    /*1号循环*/
    while (!st.empty() && x >= st.top()) {
        //如果新值和栈顶值相同（相邻且身高一样的情况），更新答案(ans)
		if (st.top() == x)lap++;
        
        //新值是满足大于等于栈顶值的，更新答案(ans)
		ans++;
        
        //通过循环依次pop出小于等于新值的栈顶元素(维护单调递减栈)
		st.pop();
	}

    //当经过上方的
    //		“循环依次pop出小于等于新值的栈顶元素” 操作之后
    //如果堆栈中还有元素存在，此元素一定比插入的新值要大
    //而且我们pop出了 小于等于新值栈顶元素 ，此元素和新值是可以互相看见的
    //↑↑↑这里即是满足了：	“如果他们之间没有人比a或b高”
	if (!st.empty())ans++;
	
    
    //针对重复的元素，要重新填会到堆栈中
    //也就是因为该操作，对于大数据的身高重复情况非常不友好
    //当堆栈相邻元素皆为一样身高时
    //每次/*1号循环*/都会将重复的元素先pop再push
    //这是一种累赘且耗时的操作，所以下方的AC代码以此优化
    /*2号循环*/while (lap--)st.push(x);		
    
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    
	int n;
	cin >> n;
	int x;
	while (n--) {
		cin >> x;
		_add(x);
	}
	cout << ans;
    
	return 0;
}

注：这是AC代码

能过大数据的一大原因就在

代码第35行pa.second += st.top().second;的操作

将相邻的同类数据给合并起来，而不是像上方的80分代码那样~~先pop再push~~

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <stack>
using namespace std;

//pair:  first 高度   second 高度的出现次数
stack< pair<int, long long> > st;

//你需要铭记的是：
//		我们这里维护的是一个 单调递减 的堆栈，栈顶为最小值
//		针对新插入元素大于栈顶的情况，需要进行处理，并对答案进行更新(ans)

//n的数量级可以达到5 * 1e5 当这些人高度都一样时，结果为：124999750000
//爆int了！！！(っ °Д °;)っ
long long ans = 0;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    
	int n;
	cin >> n;
	int x;
	while (n--) {
		cin >> x;
		pair<int, long long> pa(x, 1ll);
        
        //栈非空 新值大于栈顶值（不符合我们单调递减栈的要求）
		while (!st.empty() && x >= st.top().first) {
			/*新值和栈顶值相同（相邻且身高一样的情况）*/
			if (st.top().first == x){
                
			//因为在while循环中，我们会通过循环依次pop出小于等于新值的栈顶元素
			//所以这里是对相同元素的一个统计，这样的优化避免了上方的TLE(代码运行超时)情况
				pa.second += st.top().second;
			}
            
            //新值是满足大于等于栈顶值的，更新答案(ans)
			ans += st.top().second;

			st.pop();//通过循环依次pop出小于等于新值的栈顶元素(维护单调递减栈)
		}

        
        //当经过上方的
        //		“循环依次pop出小于等于新值的栈顶元素” 操作之后
        //如果堆栈中还有元素存在，此元素一定比插入的新值要大
        //而且我们pop出了 小于等于新值栈顶元素 ，此元素和新值是可以互相看见的
        //↑↑↑这里即是满足了：	“如果他们之间没有人比a或b高”
		if (!st.empty())ans++;

        //将新值加入到堆栈中
		st.push(pa);
	}

	cout << ans;

	return 0;
}