感谢@Cute_SilverWolf为这篇文章作出的贡献

单调栈部分

求下一个最大数

题目描述

给你nn个整数a1,a2,…,ana_1, a_2, \dots ,a_n,请问从每个数字往后看，第一个比它大的数字下标是多少？如果后面没有比它大的数字，输出0。

1≤n≤2×1051 \leq n \leq 2 \times 10 ^ 5

思路

直接暴力显然不可行

下面引入单调栈的思想，我们维护一个栈，然后从后往前遍历数组，每次我们要做这么几件事：

  • 不断把栈顶小于它的元素弹出，直到栈顶元素对应的数大于当前的数或栈为空。我们知道从这个元素之后遍历的元素肯定不会再看到那些被弹出的元素，因为肯定优先看到当前的元素。

  • 此时栈顶就是要求的答案，如果栈为空就表示后面没有比它大的数字。

  • 把当前数字的下标插入栈。

这就是单调栈的思想，时间复杂度为O(N)O \left ( N \right )

代码

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
##include<bits/stdc++.h>
using namespace std;
##define int long long
signed main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> ans;
    stack<int> st;
    for (int i = n - 1; i >= 0; i--) {
        while (st.size() && a[st.top()] <= a[i]) {
            st.pop();
        }
        ans.push_back(st.empty() ? -1 : st.top());
        st.push(i);
    }
    for (int i = n - 1; i >= 0; i--) {
        cout << ans[i] + 1 << ' ';
    }
    return 0;
}
```   

## 最大矩形面积

### 题目描述

有一个$n$列的网格图，每列有一个格子被beat从底向上染了色，现在给你每一列被涂色的格子高度$a_i$，请你求出被涂色格子组成的最大矩形面积。

$1 \leq n \leq 2 \times 10 ^ 5$

### 思路

假如我们选择了$\left [ l, r \right ]$这段区间，那么对应的矩形面积就是$(r - l + 1) \times \min \left (a_l, a_l + 1 \dots a_r \right )$。

因此答案的取值只和区间的长度和区间的最小值有关，我们对数组每个元素都假设它作为选出来区间的最小值，可以先找出来左边的哥小于它的数和右边第一个小于它的数，那对应的$l, r$就分别是左边的位置加一，右边的位置减一，这样就能保证这一整段都不小于当前元素。

对于每个元素记一下左右端点的位置，然后遍历一遍数组取最大值即可。

有些精妙了

### 代码

```cpp
##include<bits/stdc++.h>
##define int long long
using namespace std;
signed main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> l(n, 0), r(n, 0);
    stack<int> st; 
    for (int i = 0; i < n; i++) {
        while (st.size() && a[i] <= a[st.top()]) {
            st.pop();
        }
        l[i] = (st.size() ? st.top() : -1);
        st.push(i);
    }
    while (st.size()) {
        st.pop();
    }
    for (int i = n - 1; i >= 0; i--) {
        while (st.size() && a[i] <= a[st.top()]) {
            st.pop();
        }
        r[i] = (st.size() ? st.top() : n);
        st.push(i);
    }
    int ans = 0; 
    for (int i = 0; i < n; i++)  {
        ans = max(ans, a[i] * (r[i] - l[i] - 1));
    }
    cout << ans;
    return 0;
}

数对统计2

题目描述

给你nn个数字a1,a2,…,ana_1, a_2, \dots ,a_n，这些数字各不相同。问你共有多少对数字(i,j)\left ( i, j \right )，满足aia_i到aja_j中没有数字或没有数字比aia_i或aja_j大。即对所有位置k(i<k<j)k \left ( i < k < j \right )满足ak<min⁡(ai,aj)a_k < \min(a_i, a_j)

1≤n≤2×1051 \leq n \leq 2 \times 10 ^ 5

思路

发现维护一个栈顶最小的单调栈里，对于一个位置ii，从最大的位置k<ik < i满足ak>aia_k > a_i到i−1i - 1这个位置都是可以和位置ii配对的。

所以直接单调栈就做完了，每探出一次答案就加一。注意要是我们弹出完之后栈中铀元素，表示这个ii是可以和栈顶匹配的，答案继续加一。

代码

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
##include<bits/stdc++.h>
using namespace std;
##define int long long
signed main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ans = 0;
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (st.size() && a[i] >= a[st.top()]) {
            ans++;
            st.pop();
        }
        if (st.size()) {
            ans++;
        }
        st.push(i);     
    }
    cout << ans;
    return 0;
}

单调队列部分

这一部分不是数据结构就全做完了吗？单调队列我只记得拿来优化dp过来着。
——Cute_SilverWolf在复习提高组的逆天言论节选

动态区间最大数

题目描述

给你nn个数组a1,a2,…,ana_1, a_2, \dots , a_n，请从左到右输出每个长度为mm的数列段里的最大数。

这些数列段分别为[1,m],[2,m+1],…,[n−m+1,n]\left [ 1, m \right ] , \left [ 2, m + 1 \right ] , \dots , \left [ n - m + 1, n \right ]

1≤m≤n≤2×2×1051 \leq m \leq n \leq 2 \times 2 \times 10 ^ 5

思路

无脑维护单调队列，满足队顶为最大元素，所以每次插入新元素之后直接输出队顶即可。注意要是队顶超出了区间的范围，就把队顶弹出，下一个答案必定也是合法且最优的。

注意这里队首队尾都需要支持操作，我们直接手写队列。

代码

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> que(2 * n);
    int l = 0, r = -1;
    for (int i = 0; i < m - 1; i++) {
        while (l <= r && a[i] >= a[que[r]]) {
            r--;
        }
        que[++r] = i;
    }
    for (int i = m - 1; i < n; i++) {
        while (l <= r && a[i] >= a[que[r]]) {
            r--;
        }
        que[++r] = i;
        if (i - m >= que[l]) {
            l++;
        }
        cout << a[que[l]] << ' ';
    }
    return 0;
}