单调栈
Eva.Q Lv9
2022-02-02 22:21:33

Life is a journey to experience to learn and to enjoy.

单调栈

今天和Co老师学习了单调栈

定义

单调栈，就是栈内元素单调的栈。

易错点
  1. 每次访问栈内元素时，都要保证栈非空，否则会 ​ 。
  2. 栈的清空。
应用

询问Co老师，什么时候要用单调栈，Co老师说，要多做题，自己就有感觉了。但Co老师还是给了我几条：

  1. “最近”：因为栈是先入后出，所以往往栈顶的元素会比栈里的其他元素离当前元素近。
  2. “单调”：就是那种，遇到一个更优解时，栈内较劣的元素就可以不断弹掉，且能保证剩下的元素还能保证“单调性”。

其他的我好像还没悟出来，等我多做做题了，再回来补充吧。

例题

一

给一组类似于柱形图的每一个柱子的高度，宽度默认均为 1 。

求最大的矩形面积。

分析可得：S[i] = a[i] * (r[i] - l[i] + 1) （ l[i] 是以 a[i] 为高的，可延伸到最远的左端点，r[i] 同理）

这应该是一个单调增栈。

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
60
61
62
63
64
65
66
#include<stack>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define N 100007
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

stack<int> S;
int a[N], l[N], r[N];

void clearStack(){
    while(!S.empty()) S.pop();
}

inline void work(int n) {
    for (int i = 1; i <= n; ++i) {
        a[i] = rd();
    }
    clearStack();
    S.push(1); l[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (a[i] <= a[S.top()]) {
            while (!S.empty() && a[i] <= a[S.top()]) {
                l[i] = l[S.top()]; S.pop();
            }
        } else {
            l[i] = i;
        }
        S.push(i);
    }
    clearStack();
    S.push(n); r[n] = n;
    for (int i = n - 1; i >= 1; --i) {
        if (a[i] <= a[S.top()]) {
            while (!S.empty() && a[i] <= a[S.top()]) {
                r[i] = r[S.top()]; S.pop();
            }
        } else {
            r[i] = i;
        }
        S.push(i);
    }
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
       ans = max(ans, 1ll * a[i] * (r[i] - l[i] + 1));
    }
    printf("%lld\n", ans);
}

int main() {
    int n = rd();
    while (n) {work(n); n = rd();}
    return 0;
}
来做优化吧

就是说算 l[n] 要一次循环，算 r[n] 还要一次循环，浪费呀~

可以注意到 ：

若 把 弹出来，就说明 ，那所以 的 ，又因为 ，所以 肯定也知道了啊，所以其实对于被弹出来的元素其最大面积已经知道了。

优化一

在最后加一个 a[n++] = 0 

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
#include<stack>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define N 100007
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

stack<int> S;
int a[N], l[N];

void clearStack(){
    while(!S.empty()) S.pop();
}

inline void work(int n) {
    for (int i = 1; i <= n; ++i) {
        a[i] = rd(); l[i] = i;
    }
    a[++n] = 0; l[n] = n;
    ll ans = 0;
    clearStack();
    S.push(1); l[1] = 1;
    for (int i = 2; i <= n; ++i) {
        while (!S.empty() && a[i] <= a[S.top()]) {
            ans = max(ans, 1ll * a[S.top()] * (i - l[S.top()]));
            l[i] = l[S.top()]; S.pop();
        }
        S.push(i);
    }
    printf("%lld\n", ans);
}

int main() {
    int n = rd();
    while (n) {work(n); n = rd();}
    return 0;
}
优化二
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<stack>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define N 100007
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

stack<int> S;
int a[N], l[N];

void clearStack(){
    while(!S.empty()) S.pop();
}

inline void work(int n) {
    for (int i = 1; i <= n; ++i) {
        a[i] = rd(); l[i] = i;
    }
    ll ans = 0;
    clearStack();
    S.push(1); l[1] = 1;
    for (int i = 2; i <= n; ++i) {
        while (!S.empty() && a[i] <= a[S.top()]) {
            ans = max(ans, 1ll * a[S.top()] * (i - l[S.top()]));
            l[i] = l[S.top()]; S.pop();
        }
        S.push(i);
    }
    while (!S.empty()) {
        ans = max(ans, 1ll * a[S.top()] * (n - l[S.top()] + 1));
        S.pop();
    }
    printf("%lld\n", ans);
}

int main() {
    int n = rd();
    while (n) {work(n); n = rd();}
    return 0;
}
二

洛谷

给出项数为 的整数数列 。

定义函数 代表数列中第 个元素之后第一个大于 的元素的下标，即 。若不存在，则 。

试求出 。

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
#include<stack>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define N 3000007
typedef long long ll

inline ll rd() {
  ll x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

stack<int> S;
ll a[N];
int f[N];

void clearStack(){
    while(!S.empty()) S.pop();
}

inline void work(int n) {
    for (int i = 1; i <= n; ++i) {
        a[i] = rd();
    }
    clearStack(); S.push(n);
    for (int i = n - 1; i >= 1; --i) {
        while (!S.empty() && a[i] >= a[S.top()]) S.pop();
        if (!S.empty()) f[i] = S.top();
        S.push(i);
    }
    for (int i = 1; i <= n; ++i) {
        printf("%d ", f[i]);
    }
}

int main() {
    work(rd());
    return 0;
}
三

洛谷 

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
#include<stack>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define N 250007
typedef long long ll;

inline ll rd() {
  ll x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

stack<ll> S;
ll a[N];

void clearStack(){
    while(!S.empty()) S.pop();
}

inline void work(ll n) {
    for (ll i = 1; i <= n; ++i) {
        a[i] = rd(); a[i] = rd();
    }
    ll ans = n;
    clearStack();
    S.push(1);
    for (ll i = 2; i <= n; ++i) {
        while (!S.empty() && a[i] < a[S.top()]) {
            S.pop();
        }
        if (!S.empty() && a[S.top()] == a[i]) {ans--; S.pop();}
        S.push(i);
    }
    printf("%lld\n", ans);
}

int main() {
    work(rd());
    return 0;
}
四

洛谷

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

首先，如果 能看到 ， 一定能看到 。为了避免重复计算，且好写代码（em……）。我们只需要计算每一个人往队伍后面看能看到多少个人，再将答案相加即可。

对于一个位置 ，所有他可能看见的人满足以下条件：

  1. 这些人是按照队伍里的位置，组成的序列是非降的，即如果 和 都可能被 看到，且在队伍中 排在 的前面，那 ​。

    由此可知，单调栈里应该是非降序，即下面的元素要大于等于上面的元素。

  2. 如果前一个人已经比 高了，那后面的人，就无法被 看到了。

再考虑整个队伍，后面的人弹掉的那些元素，会不会影响前面的人的正确答案。假设两个人在队伍中， 在 的前面， 能看到的是单调栈里面比自己矮的和第一个比自己高的，比 矮的弹掉不会影响 的答案，因为 一定看不到他们。跟 等高的又需要计入 的答案，且还应当保留在单调栈中。故我们在单调栈中存放二元组，记录高度，和该高度的个数，最后塞入单调栈中。

对于每一次 while 循环，其退出有两种条件：

  1. 栈空了
  2. 栈顶元素比当前元素大

如果是 1. 那答案就是循环里算出的答案，如果是 2. 答案则需 +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
#include<stack>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define N 500007
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

stack<pair<int, int> > S;
int a[N];
ll ans = 0;

void clearStack(){
    while(!S.empty()) S.pop();
}

inline void work(int n) {
    for (int i = 1; i <= n; ++i) {
        a[i] = rd();
    }
    clearStack();
    S.push(make_pair(n, 1));
    for (int i = n - 1; i >= 1; --i) {
        int cnt = 1;
        while (!S.empty() && a[i] >= a[S.top().first]) {
            ans += S.top().second;
            if (a[i] == a[S.top().first]) cnt += S.top().second;
            S.pop();
        }
        ans += (!S.empty());
        S.push(make_pair(i, cnt));
    }
    printf("%lld\n", ans);
}

int main() {
    work(rd());
    return 0;
}
五

洛谷

给一个 ​ 的二维矩阵，求最大矩形面积。

枚举答案矩形的底边，就可以将题目转换为 题目一 

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
60
61
62
#include<stack>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define N 1007
typedef long long ll;

inline int rd() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

stack<int> S;
int f[N][N], l[N], n, m;
char a[N][N];

void clearStack(){
    while(!S.empty()) S.pop();
}

inline ll solve(int x) {
    ll ans = 0;
    clearStack();
    S.push(1);
    for (int i = 1; i <= m; ++i) l[i] = i;
    for (int i = 2; i <= m; ++i) {
        while (!S.empty() && f[x][i] <= f[x][S.top()]) {
            ans = max(ans, 1ll * f[x][S.top()] * (i - l[S.top()]));
            l[i] = l[S.top()]; S.pop();
        }
        S.push(i);
    }
    while (!S.empty()) {
        ans = max(ans, 1ll * f[x][S.top()] * (m - l[S.top()] + 1));
        S.pop();
    }
    return ans;
}

inline void work() {
    n = rd(), m = rd();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            for (a[i][j] = getchar(); a[i][j] != 'F' && a[i][j] != 'R'; a[i][j] = getchar());
            f[i][j] = (a[i][j] == 'F') ? f[i - 1][j] + 1 : 0;
        }
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {ans = max(ans, solve(i));}
    printf("%lld\n", 3 * ans);
}

int main() {
    work();
    return 0;
}
  • Post title：单调栈
  • Post author：Eva.Q
  • Create time：2022-02-02 22:21:33
  • Post link：https://qyy/2022/02/02/Algorithm/Monotonic stack/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.