单调栈专项练习

七月 21, 2019 8236

单调数据结构

练习：洛谷P2947《Look Up》

题目描述

Farmer John’s N (1 <= N <= 100,000) cows, conveniently numbered 1..N, are once again standing in a row. Cow i has height H_i (1 <= H_i <= 1,000,000).

Each cow is looking to her left toward those with higher index numbers. We say that cow i ‘looks up’ to cow j if i < j and H_i < H_j. For each cow i, FJ would like to know the index of the first cow in line looked up to by cow i.

Note: about 50% of the test data will have N <= 1,000.

约翰的N(1≤N≤10^5)头奶牛站成一排，奶牛i的身高是Hi(l≤Hi≤1,000,000)．现在，每只奶牛都在向右看齐．对于奶牛i，如果奶牛j满足i<j且Hi<Hj，我们可以说奶牛i可以仰望奶牛j． 求出每只奶牛离她最近的仰望对象．

Input

输入输出格式

输入格式

  • Line 1: A single integer: N

  • Lines 2..N+1: Line i+1 contains the single integer: H_i

第 1 行输入 N，之后每行输入一个身高 H_i。

输出格式

  • Lines 1..N: Line i contains a single integer representing the smallest index of a cow up to which cow i looks. If no such cow exists, print 0.

共 N 行，按顺序每行输出一只奶牛的最近仰望对象，如果没有仰望对象，输出 0。

输入输出样例

输入样例

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

输出样例

1
2
3
4
5
6
3 
3 
0 
6 
6 
0

说明

FJ has six cows of heights 3, 2, 6, 1, 1, and 2.

Cows 1 and 2 both look up to cow 3; cows 4 and 5 both look up to cow 6; and cows 3 and 6 do not look up to any cow.

【输入说明】6 头奶牛的身高分别为 3, 2, 6, 1, 1, 2.

【输出说明】奶牛#1,#2 仰望奶牛#3，奶牛#4,#5 仰望奶牛#6，奶牛#3 和#6 没有仰望对象。

【数据规模】

对于 20%的数据： 1≤N≤10；

对于 50%的数据： 1≤N≤1,000；

对于 100%的数据：1≤N≤100,000；1≤H_i≤1,000,000；

解析

题目就是说，依次给出一堆线段，求对于每条线段，第一个在它右面，长度大于它的线段的下标是多少
我们先来模拟一下：

1
2
3
4
5
6
1[===] 歪着看体验更佳（逃
2[==]
3[======]
4[=]
5[=]
6[==]

第一次，1号进来了，没有比它高的，让它等一会
第二次，2号进来了，它甚至比1号还低，对1号的答案没有什么影响，也让它等一会
第三次，3号进来了，它比1、2号都高！此时1、2号的答案都是3号，而且1、2号对于以后的线段答案是没有影响的，呆在队伍里已经没有什么用了，让它们出去即可
第四次、第五次，4号和5号依次进来，对3号的答案并没有什么影响
第六次，6号进来了，4号和5号的答案更新为6号，而且对以后的线段答案也是没有什么影响的（如果以后还有线段的话），出去即可
队伍里还有俩线段3和6，它们的答案没有被更新过，也就是没有答案

这就是一个单调栈的工作流程，通过清除栈里的元素来维护单调性，而本题中第三次循环和第六次循环则是对于单调数据结构进行具体问题具体分析的关键点

可以看出，实质上是维护了一个单调不增的栈，在维护栈的单调性过程中求出了答案

代码实现

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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define rep(a,s,t,i) for (int a = s; a <= t; a += i)
#define repp(a,s,t,i) for (int a = s; a < t; a += i)
#define countdown(s) while (s --> 0)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

int getint() { int x; scanf("%d", &x); return x; }
long long int getll() { long long int x; scanf("%lld", &x); return x; }

const int MAXN = 100000 + 10;

int n, ans[MAXN];

struct Cow {
    int height, id;
    
    Cow() : height(0), id(0) {}
    Cow(int height, int id) : height(height), id(id) {}
};

std::stack<Cow> stk;

int main() {
    n = getint();
    rep (i, 1, n, 1) {
        int height = getint();
        while (!stk.empty() && stk.top().height < height) {
            // stk.top().height < height 维护栈内元素单调不增性
            // 如果 stk.top().height > height 则单调性仍存在，不必维护
            ans[stk.top().id] = i;
            // 更新答案
            stk.pop();
        }
        stk.push((Cow) { height, i });
    }
    rep (i, 1, n, 1) { printf("%d\n", ans[i]); }
    return 0;
}


巩固：洛谷P1901《发射站》

题目描述

某地有 N 个能量发射站排成一行，每个发射站 i 都有不相同的高度 Hi，并能向两边（当 然两端的只能向一边）同时发射能量值为 Vi 的能量，并且发出的能量只被两边最近的且比 它高的发射站接收。

显然，每个发射站发来的能量有可能被 0 或 1 或 2 个其他发射站所接受，特别是为了安 全，每个发射站接收到的能量总和是我们很关心的问题。由于数据很多，现只需要你帮忙计 算出接收最多能量的发射站接收的能量是多少。

输入输出格式

输入格式

第 1 行：一个整数 N;

第 2 到 N+1 行：第 i+1 行有两个整数 Hi 和 Vi，表示第 i 个人发射站的高度和发射的能量值。

输出格式

输出仅一行，表示接收最多能量的发射站接收到的能量值，答案不超过 longint。

输入输出样例

输入样例#1

1
2
3
4
3
4 2 
3 5 
6 10

输出样例#1

1
7

说明

对于 40%的数据，1<=N<=5000；1<=Hi<=100000；1<=Vi<=10000;

对于 70%的数据，1<=N<=100000；1<=Hi<=2,000,000,000；1<=Vi<=10000;

对于 100%的数据，1<=N<=1000000;1<=Hi<=2,000,000,000；1<=Vi<=10000。

解析

同样的，先来模拟一下这个过程：

1
2
3
1[====](2)
2[===](5)
3[======](10)

第一次，1号发射站进来，它莫得其他发射站来传输能量
第二次，2号发射站进来，它可以给1号传输能量
第三次，3号发射站进来：
2号发射站可以给3号发射站传输能量，1号发射站亦可。由于这两个发射站对于其他发射站的答案已经没有贡献，自己的答案也确定了，让它们出去即可

本质上也是维护了一个单调递减的栈，在维护单调性的同时确定答案

代码实现

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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define rep(a,s,t,i) for (int a = s; a <= t; a += i)
#define repp(a,s,t,i) for (int a = s; a < t; a += i)
#define countdown(s) while (s --> 0)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

int getint() { int x; scanf("%d", &x); return x; }
long long int getll() { long long int x; scanf("%lld", &x); return x; }

struct Launcher {
    int id;
    int height; long long int energy;
    // height: 该发射站的高度
    // energy: 该发射站的能量强度
    Launcher() { id = height = energy = 0; }
    Launcher(int id, int height, long long int energy) : id(id), height(height), energy(energy) {}
};

const int MAXN = 1000000 + 10;

int n;
long long int ans[MAXN]; // 答案不超过 long int
std::stack<Launcher> stk;

int main() {
    n = getint();
    rep (i, 1, n, 1) {
        int h = getint();
        int energy = getint();
        while (!stk.empty() && stk.top().height < h) {
            ans[i] += stk.top().energy; // 栈顶对应的发射站能「向右」发射能量到当前的发射站
            stk.pop(); // 维护栈的单调递减性
        }
        if (!stk.empty()) ans[stk.top().id] += energy; // 当前发射站能「向左」发射能量到栈顶对应的发射站
        stk.push((Launcher) { i, h, energy });
    }
    printf("%lld\n", (long long int) *std::max_element(ans + 1, ans + 1 + n));
    return 0;
}


提高：洛谷P1823《Patrik 音乐会的等待》

题目描述

N个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。队列中任意两个人A和B，如果他们是相邻或他们之间没有人比A或B高，那么他们是可以互相看得见的。

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

输入输出格式

输入格式

输入的第一行包含一个整数N (1 ≤ N ≤ 500 000), 表示队伍中共有N个人。

接下来的N行中，每行包含一个整数，表示人的高度，以毫微米(等于10的-9次方米)为单位，每个人的调度都小于2^31毫微米。这些高度分别表示队伍中人的身高。

输出格式

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

输入输出样例

输入样例#1

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

输出样例#1

1
10

解析

依然来模拟一下：，

1
2
3
4
5
6
7
1[==]
2[====]
3[=]
4[==]
5[==]
6[=====]
7[=]

第一次，1号进入，它谁都望不到
第二次，2号进入，1、2号能互相看见，此时1号对答案已经没有贡献，出去即可
第三次，3号进入，2、3号能互相看见
第四次，4号进入，3、4号能互相看见，同时2、4号也可以互相看见，此时3号对答案已经没有贡献，出去即可
第五次……第六次……第七次……

已经很明显了，依然是维护一个单调不增的栈，在维护元素单调性的同时更新答案
但是这里的代码实现有一定的技巧

代码实现

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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define rep(a,s,t,i) for (int a = s; a <= t; a += i)
#define repp(a,s,t,i) for (int a = s; a < t; a += i)
#define countdown(s) while (s --> 0)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

int getint() { int x; scanf("%d", &x); return x; }
long long int getll() { long long int x; scanf("%lld", &x); return x; }

struct Height {
    // 按照顺序把相邻等高的人视为一组
    int height; long long int amount;
    // height: 该组的高度
    // amount: 该组的人数
    Height() { height = amount = 0; }
    Height(int height, long long int amount) : height(height), amount(amount) {}
};

int n;
long long int ans;
std::stack<Height> stk;

int main() {
    n = getint();
    rep (i, 1, n, 1) {
        int h = getint();
        Height hh = (Height) { h, 1 };
        while (!stk.empty() && stk.top().height <= h) {
            ans += stk.top().amount; // 当前人能够看见上一组整组的人
            if (stk.top().height == h) hh.amount += stk.top().amount; // 如果两组人等高，就把两组人归到一组去
            stk.pop();
        }
        if (!stk.empty()) ++ans;
        // 在放当前的人进栈之前，如果栈非空，说明栈顶这个人是能看见当前的人的
        stk.push(hh);
    }
    printf("%lld\n", ans);
    // C(100000, 2) > (1 << 31)
    // 答案超过 int
    return 0;
}