单调栈

## 前置知识： 1：栈的运用 ## 何为单调栈？ 从字面意思上来看，无非就是有某种**单调性**的栈。 一般解释，就是栈内**所有**元素按照所维护的值**递增/递减**顺序排列的栈。 ## 单调栈有何用？ 单调栈分两种，一种是单调**递增**栈，一种是单调**递减**栈。一般来说，单调栈解决的问题是求某个元素下一个比其**大/小**的元素。 所以，当我们解决比较前后元素的**大小**关系时，我们就可以使用单调栈。 ## 如何解决？ 此处借鉴天天~的奇思妙想使读者更好地理解... 我们可以先模拟一下单调栈的过程。 假如有一天~~修仙~~武林高手石破天要传授神功《太玄经》，各路武林高手都想学，于是就到石破天家门口排队，但石破天大侠并不喜欢来的晚的人，所以就按照人来的先后顺序教，先来的学的武功就高深，来的越靠后学的就越差，但是可以保证只要来学武功的人都能学到。  当然，即使是内功高手扫地僧也想要这么一副神功，所以任何人当然是想学的越高深越好。所以每当有武功高的人就会找到前面武功稍逊的人说：“你别去学了，我这里有本武功更适合你。” 武功稍逊的那一个一听就答应了 ~~（就算不答应也打不过啊...）~~，从其哪里学了一门武术高高兴兴的走了，这样武功高的那个就排在了前面。 下面我们来从前往后模拟一下过程： 1. 首先来的是炮灰甲，炮灰甲一看，OK，栈内没有人就可以先排在第一位 2. 然后扫地僧来了，扫地僧教给了炮灰甲自己的功夫，然后扫地僧让炮灰甲离开自己排在第一位 3. 然后杨过过来，看到前面是扫地僧，自己打不过只能老老实实站到队里 4. 后面一直来人，但都打不过前面的人，直到张三，（队列：扫地僧 杨过 慕容复 张三） 5. 然后张无忌来了，他首先看到前面是张三，张无忌教给张三自己的功夫并让他离开），然后张无忌再往前看到了慕容复（过程如上所示），直到遇到扫地僧，OK，自己打不过，老老实实的占到了后面，（杨过，慕容复，张三的师傅为张无忌）。（队列：扫地僧，张无忌） 6. 柯镇恶来了，自己打不过扫地僧，只能站在后面。 7. 然后乔峰来了把柯镇恶和张无忌打发走。（队列：扫地僧，乔峰） 8. 然后李四来了，打不过乔峰，只能站到了最后。 9. 最后扫地僧，乔峰，李四成功学到了~~修仙~~武林秘籍《太玄经》。 武功对应：  这样我们就模拟完了一个**单调递减栈**的过程，由于每个元素只会留在栈中或被弹走一次，所以时间复杂度为 $O(n)$ 。 ```cpp while (!stk.empty() && a[i] <= a[stk[top]]) { // 打得过 a[stk[top]] = i; // 教授武功 top--; // 赶走 } stk[++top] = i; // 入栈 ``` Tip： 栈中存的不是**值**，而是**下标**。 ------------ ## 如何应用？ [LG2422 良好的感觉](https://www.luogu.com.cn/problem/P2422) ### 题意： 给定一个长度为 $n(1≤n≤100,000)$ 的正整数序列 $P$ ，求任意区间中，**区间最小值 × 区间和**的最大值。 ### 分析： 对于每个区间我们可以用朴素的做法暴力枚举一遍，然后再求每个区间的**区间最小值**和**区间和**，时间复杂度为 $O(n ^ 3)$ 。 在此之上我们可以用**前缀和**预处理，这要我们求每个区间和的时间复杂度只有 $O(1)$ 。 现在我们可以利用一个**贪心**的思想，如果在一个正整数序列任意区间内，区间最小值 $P_i$ 都是**确定**的，**区间长度越长，那么对于答案就更优**。 所以说我们可以去维护每一个 $P_i$ 所在的所有区间中，满足在此区间中 $P_i$ 最小的区间的**左右下标**，再利用**前缀和**，求出以每一个 $P_i$ 当区间最小值的 $Ans$ 中取最大值。 这时候我们就可以用单调栈来维护。 ```cpp #include<bits/stdc++.h> using namespace std; inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if(c == '-') { f = -1; } c = getchar(); } while (c <= '9' && c >= '0') { x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); } return x * f; } const int Maxn = 2e5 + 5; int n, top, a[Maxn], stk[Maxn], L[Maxn], R[Maxn]; long long ans = 0, sum[Maxn]; int main() { n = read(); for (register int i = 1; i <= n; ++i) { a[i] = read(); sum[i] = a[i] + sum[i - 1]; // 预处理前缀和 } top = 0; // 用数组模拟栈，初始化栈顶 for (register int i = 1; i <= n; ++i) { while (top > 0 && a[i] <= a[stk[top]]) { // 如果此时栈顶比当前 a[i] 要小 R[stk[top--]] = i; // 记录 R数组 ，并将栈顶弹出 } stk[++top] = i; // 插入栈顶 } for (register int i = 1; i <= n; ++i) { // 记录剩下栈中元素，他们的右边没有比他们小的 if(R[i] == 0) { R[i] = n + 1; // 边界 } } top = 0; for (register int i = n; i >= 1; --i) { // L数组 记录过程同 R数组 while (top > 0 && a[i] <= a[stk[top]]) { L[stk[top--]] = i; } stk[++top] = i; } for (register int i = 1; i <= n; ++i) { ans = max(ans, (sum[R[i] - 1] - sum[L[i]]) * a[i]); // 对于每个 a[i] 求其对于的 Ans，取最大值 } printf("%lld\n", ans); return 0; } ``` 另外，我们还有一种做法。 可以考虑，对于此序列中的最大值，在没有重复的情况下，他的 $L$ 和 $R$ 都只是它自己的下标，而对于第二大值，除了最大值和重复， $L$ 和 $R$ 都只是它自己的下标，如果有了最大值和重复，我们就可以去**继承**最大值和重复所对应的 $L$ 和 $R$ ，并且我们可以用**并查集**去维护。 [POI2008 PLA-Postering](https://www.luogu.com.cn/problem/P3467) ### 题意： 给定 $n$ 个海报，排成一排。现在希望用尽量少的矩形海报 $Cover$ 住它们，且不能超出边界。 ### 分析： **所有的形状，无非就是一个凹字形或一个凸字形排列起来的。**  假如成“凹”字形： 那么那一块空白会把旁边两块海报隔开，还是需要**三块海报**。  假如成“凸”字形： 我们只需要**两块海报**。 所以我们到这里可以想到维护一个**单调递增**的栈，如果遇到一个新的建筑如果比上一个矮，就删掉上一个海报，**直到上一块海报的值小于它**。 如果删除过程中有一块海报与其**相等**，那么我们就只要用**一块海报**覆盖掉，这块海报在之前就被计算过了，那就比原先的海报少一块。 否则，答案就不用变，因为**没有可以节省的海报**。 宽度无用... ### 代码： ```cpp #include<bits/stdc++.h> using namespace std; inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if(c == '-') { f = -1; } c = getchar(); } while (c <= '9' && c >= '0') { x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); } return x * f; } const int Maxn = 250052; int n, ans, top, h[Maxn], s[Maxn]; int main() { n = ans = read(); int di; // 宽度无用 for (register int i = 1; i <= n; ++i) { di = read(), h[i] = read(); while (s[top] > 0 && h[i] <= h[s[top]]) { // 比较栈顶 if(h[i] == h[s[top]]) { // 如果相等 ans--; // 节约一张海报 } top--; } s[++top] = i; } printf("%d\n", ans); return 0; } ``` [CF1299C Water Balance](https://codeforces.com/contest/1299/problem/C) ### 题意： 给定一个长度为 $n(1≤n≤1,000,000)$ 的正整数序列 $P$ ，有一操作可以使**任意区间**的数，都变成此区间的**平均数**。 最后能得到的**字典序最小**的结果（即满足越前面的数越小越好）。 ### 分析： 通过观察，可以发现，答案序列中的数都是**单调不下降**的。因为如果出现下降字段的话，那么我们可以继续操作使得答案更优。 反之，如果想得到答案，我们就**必须**是序列不下降；并且如果序列不下降，那么答案字典序就最小。 故，结论：**只要通过操作使整个数列不下降，那么它就是答案。** 所以我们可以使用**单调栈**维护每个取过平均数的区间，每次新加进来一个数的时，如果它能使栈顶的区间平均数更小，那么就可以利用**贪心**的思想，将它与这个区间**合并**。合并之后，再与栈顶对应的区间能不能使栈中在它下面的区间平均数**更小**，再进行合并。 如此反复，直到单调栈中的元素**单调递增**（不相等是因为平均数相等的区间可以直接合并）。由于上面的结论可知，这种方法能得到最终答案。 那么如何判断区间能否合并呢？其实我们只需要**比较平均数**即可，后面的区间如果比前面的区间平均数小，那么就可以合并。对于计算新区间的平均数，只需要维护两个区间的**左端点，右端点和平均数**，将其求和后再求平均数即可。 最后的分段结果保存在栈中，由于栈顶保存的是最后一个区间，所以需要递归倒序输出。 借用于[一只大头](https://www.luogu.com.cn/blog/lcm2019/solution-cf1299c)的题解，欢迎去膜拜评论。 ### 代码： ```cpp #include<bits/stdc++.h> using namespace std; inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') { f = -1; } c = getchar(); } while (c <= '9' && c >= '0') { x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); } return x * f; } const int MaxN = 1000010; int n; double a[MaxN]; struct Node { int l, r; double val; Node () { l = r = val = 0; } Node (int l = 0, int r = 0, double val = 0) : l(l), r(r), val(val) { } }; inline double Calc (Node a) { return a.val * (a.r - a.l + 1); } stack <Node> s; inline void Update (int x) { Node p = Node(s.top().l, x, (Calc(s.top()) + a[x]) / (x - s.top().l + 1)); s.pop(); while (s.empty() == false && p.val < s.top().val) { Node cur = s.top(); s.pop(); p.val = (Calc(p) + Calc(cur)) / (p.r - cur.l + 1); p.l = cur.l; } s.push(p); return ; } inline void Put () { if (s.empty() == true) { return ; } Node tmp = s.top(); s.pop(); Put(); for (register int i = tmp.l; i <= tmp.r; i++) { printf("%.9lf\n", tmp.val); } return ; } int main() { n = read(); for (register int i = 1; i <= n; ++i) { a[i] = read(); } for (register int i = 1; i <= n; ++i) { if (s.empty() == true || a[i] > s.top().val) { s.push(Node(i, i, a[i])); } else { Update(i); } } Put(); return 0; } ``` [POI2008 PLA-Postering](https://www.luogu.com.cn/problem/P3467) ### 题意： 给定一个长度为 $n(1≤n≤200,000)$ 的正整数序列 $P$ ，求长度从 $1$ 到 $n$ 的区间中，所有**区间中最小值**的最大值。 ### 分析： 我们可以发现其与[LG2422 良好的感觉](https://www.luogu.com.cn/problem/P2422)有着一样的地方，我们同样可以维护每个点的**左右边界**，最后再将输出修改一下即可。 ### 代码： ```cpp #include<bits/stdc++.h> using namespace std; inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if(c == '-') { f = -1; } c = getchar(); } while (c <= '9' && c >= '0') { x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); } return x * f; } const int Maxn = 2e5 + 5; int n, top, a[Maxn], stk[Maxn], L[Maxn], R[Maxn], res[Maxn]; int main() { n = read(); for (register int i = 1; i <= n; ++i) { a[i] = read(); } top = 0; for (register int i = 1; i <= n; ++i) { while (top > 0 && a[i] < a[stk[top]]) { R[stk[top--]] = i - 1; } stk[++top] = i; } for (register int i = 1; i <= n; ++i) { if(R[i] == 0) { R[i] = n; } } top = 0; for (register int i = n; i >= 1; --i) { while (top > 0 && a[i] < a[stk[top]]) { L[stk[top--]] = i + 1; } stk[++top] = i; } for (register int i = 1; i <= n; ++i) { if(L[i] == 0) { L[i] = 1; } } for (register int i = 1; i <= n; ++i) { res[R[i] - L[i] + 1] = max(res[R[i] - L[i] + 1], a[i]); } for (register int i = n; i >= 1; --i) { res[i] = max(res[i], res[i + 1]); } for (register int i = 1; i <= n; ++i) { printf("%d ", res[i]); } puts(""); return 0; } ``` [CF817D Imbalanced Array ](http://codeforces.com/contest/817/problem/D) ### 题意： 给定一个长度为 $n(1≤n≤200,000)$ 的序列 $P$。对于给定由 $n$ 个元素构成的序列，一个子数组的不平衡值是这个区间的最大值与最小值的差值。数组的不平衡值是它所有子数组的不平衡值的总和。 ### 分析： 此题题面翻译的有些复杂，简而言之，就是求所有连续子序列中，**最大值 $-$ 最小值 的总和**。 所以我们其实只根据**乘法原理**来求出 最大 $=$ $\sum_{i=1}^n$ $a[i] * (i - L_{max}[i]) * (R_{max}[i] - i)$ 最小 $=$ $\sum_{i=1}^n$ $a[i] * (i - L_{min}[i]) * (R_{min}[i] - i)$ 然后相减即可。 ### 代码： ```cpp #include <bits/stdc++.h> using namespace std; inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') { f = -1; } c = getchar(); } while (c <= '9' && c >= '0') { x = (x << 1) + (x << 3) + (c ^ 48), c = getchar(); } return x * f; } const int INF = ~(1 << 31); const int MaxN = 1e6 + 5; long long n, top, ans = 0, a[MaxN], stk[MaxN], Max_L[MaxN], Max_R[MaxN], Min_L[MaxN], Min_R[MaxN]; int main() { n = read(); for (register int i = 1; i <= n; ++i) { a[i] = read(); } a[0] = INF; top = 1; stk[1] = 0; for (register int i = 1; i <= n; ++i) { while (a[i] >= a[stk[top]]) { top--; } Max_L[i] = stk[top]; stk[++top] = i; } a[n + 1] = INF; top = 1; stk[1] = n + 1; for (register int i = n; i >= 1; --i) { while (a[i] > a[stk[top]]) { top--; } Max_R[i] = stk[top]; stk[++top] = i; } a[0] = -2147483647; top = 1; stk[1] = 0; for (register int i = 1; i <= n; ++i) { ans += a[i] * (i - Max_L[i]) * (Max_R[i] - i); // 最大值 } for (register int i = 1; i <= n; ++i) { while (a[i] <= a[stk[top]]) { top--; } Min_L[i] = stk[top]; stk[++top] = i; } a[n + 1] = -2147483647; top = 1; stk[1] = n + 1; for (register int i = n; i >= 1; --i) { while (a[i] < a[stk[top]]) { top--; } Min_R[i] = stk[top]; stk[++top] = i; } for (register int i = 1; i <= n; ++i) { ans -= a[i] * (i - Min_L[i]) * (Min_R[i] - i); // 最小值 } printf("%lld\n", ans); return 0; } ``` 课后作业：CF5E Bindian Signalizing ## 总结： 1. 单调栈，可以简单理解为不会从队头出只会从队尾出的[单调队列](https://xyzl.blog.luogu.org/DQ-OP-DP)，**但只能从队尾取出。** 2. 单调栈一般所维护的是元素前后**大小**的关系。 3. 由于单调栈个元素同单调队列一样只进出一次，所以基本复杂度是**线性**的。