信奥赛C++提高组csp-s之单调栈详解

信奥赛C++提高组csp-s之单调栈详解

一、单调栈核心概念

单调栈是一种特殊的栈结构，栈内元素始终保持单调递增或递减的顺序。核心应用场景：快速寻找序列中每个元素左/右侧第一个比它大（或小）的元素。

时间复杂度：O(n)，每个元素至多入栈、出栈一次

二、数组模拟栈的优势

1. 执行效率高于STL的stack容器
2. 内存连续访问，缓存命中率高
3. 更适合算法竞赛的严苛性能要求

// 数组模拟栈通用写法constintMAXN=3e6+5;intstk[MAXN],top=0;// 栈和栈顶指针// 入栈操作stk[++top]=value;// 出栈操作top--;

三、案例1：找左侧第1个比当前元素小的元素

题目描述：给定长度为n的正整数序列，输出每个数之前第一个小于它的数（如果没有，输出0）

**数据规模：**n≤10 6 10^6106

输入样例：

5 1 4 2 3 5

输出样例：

0 1 1 2 3

解题思路

1. 维护单调递增栈（栈顶最大）
2. 正序遍历数组（从左向右）
3. 如果当前元素 ≤栈顶元素时，持续弹出栈顶
4. 记录第一个小于当前元素的栈顶元素
5. 当前元素入栈

AC代码

#include<iostream>usingnamespacestd;constintN=1e6+10;// 定义常量N，作为栈的最大可能大小intn,x;// n: 序列长度; x: 当前读取的数值intst[N],top=0;// st: 模拟栈的数组; top: 栈顶指针（初始为0）intmain(){cin>>n;// 读取序列长度nfor(inti=1;i<=n;i++){// 遍历序列中的每个元素cin>>x;// 读取当前元素x// 维护单调栈：弹出栈顶所有大于等于x的元素while(top!=0&&x<=st[top]){top--;}// 如果栈为空，说明前面没有比x小的数，输出0if(top==0){cout<<0<<" ";}// 否则，栈顶元素就是x之前第一个比它小的数else{cout<<st[top]<<" ";}// 将当前元素x压入栈中st[++top]=x;}return0;}

算法思路

• 单调栈：
  • 维护一个栈，栈中元素始终保持单调递增的顺序。
  • 对于当前元素x，从栈顶开始弹出所有大于等于x的元素。这样做的目的是确保栈中剩下的元素都比x小，且栈顶是离x最近的比它小的数。
  • 如果栈为空，说明前面没有比x小的数，输出0；否则输出栈顶元素。
  • 最后将x压入栈中，继续处理下一个数。

时间复杂度

• 每个元素最多入栈和出栈一次，因此时间复杂度为O(n)，能够高效处理大规模数据（n ≤ 1e6）。

关键点

1. 单调栈的性质：栈内元素始终单调递增，可以快速找到第一个比当前数小的数。
2. 栈的操作：
   • 弹出操作：移除无效元素（大于等于当前数的元素）。
   • 输出结果：栈顶元素或0。
   • 压入操作：将当前数加入栈中，维护单调性。

示例流程

以输入1 4 2 3 5为例：

1. 1：栈空 → 输出0，栈[1]；
2. 4：栈顶1<4→ 输出1，栈[1, 4]；
3. 2：弹出4（4 >= 2），栈顶1<2→ 输出1，栈[1, 2]；
4. 3：栈顶2<3→ 输出2，栈[1, 2, 3]；
5. 5：栈顶3<5→ 输出3，栈[1, 2, 3, 5]。

最终输出：0 1 1 2 3。

四、案例2：找右侧第1个比当前元素大的元素（如果没有，输出0）

题目描述：给定长度为n的正整数序列，输出每个数之后第一个大于它的数

**数据规模：**n≤10 6 10^6106

输入样例：

5 1 4 2 3 5

输出样例：

4 5 3 5 0

解题思路

1. 维护单调递减栈（栈顶最小）
2. 逆序遍历数组（从右往左）
3. 如果当前元素 ≥栈顶元素时，持续弹出栈顶
4. 记录第一个大于当前元素的栈顶元素
5. 当前元素入栈

代码实现

#include<iostream>usingnamespacestd;constintN=1e6+10;// 定义常量N，为数组的最大长度intn,a[N];// n为序列长度，a数组存储输入的序列intst[N],top=0;// st数组模拟栈，top为栈顶指针intres[N];// res数组存储结果intmain(){cin>>n;// 输入序列长度nfor(inti=1;i<=n;i++)cin>>a[i];// 输入序列// 从后往前遍历序列for(inti=n;i>=1;i--){// 维护单调栈：弹出栈顶所有小于等于当前元素的元素while(top!=0&&a[i]>=st[top]){top--;}// 如果栈为空，说明当前元素之后没有比它大的数，结果为0if(top==0){res[i]=0;}// 否则，栈顶元素就是当前元素之后第一个比它大的数else{res[i]=st[top];}// 将当前元素压入栈中st[++top]=a[i];}// 输出结果for(inti=1;i<=n;i++){cout<<res[i]<<" ";}return0;}

算法思路

1. 单调栈：使用单调栈来高效地找到每个元素之后第一个比它大的元素。栈中维护的是一个单调递减的序列。
2. 逆向遍历：从后往前遍历数组，这样可以保证栈中保存的是当前元素之后的元素，且栈顶是离当前元素最近的元素。
3. 栈操作：
   • 对于当前元素，弹出栈中所有小于或等于它的元素。因为这些元素不可能成为前面元素的目标（当前元素比它们大且更靠前）。
   • 如果栈为空，说明当前元素之后没有比它大的元素，结果为0。
   • 否则，栈顶元素就是当前元素之后第一个比它大的元素。
   • 将当前元素压入栈中。
4. 输出结果：正向遍历结果数组并输出。

时间复杂度

• O(n)。每个元素最多入栈和出栈一次，因此总的时间复杂度是线性的。

示例演示

以输入样例1 4 2 3 5为例：

1. 初始化：i = 5，a[5] = 5，栈为空，res[5] = 0，栈变为[5]。
2. i = 4，a[4] = 3，栈顶5 > 3，res[4] = 5，栈变为[5, 3]。
3. i = 3，a[3] = 2，栈顶3 > 2，res[3] = 3，栈变为[5, 3, 2]。
4. i = 2，a[2] = 4，弹出2和3（因为4 >= 2和4 >= 3），栈顶5 > 4，res[2] = 5，栈变为[5, 4]。
5. i = 1，a[1] = 1，栈顶4 > 1，res[1] = 4，栈变为[5, 4, 1]。

最终结果数组为[4, 5, 3, 5, 0]。

五、经典题型解析：洛谷P2866 [USACO06NOV] Bad Hair Day S

思路分析

1. 搞清楚方向：第1头牛在最后面（左），第n头牛在最前面（右）
2. 问题转化为：计算每头牛能被左侧的多少头牛看到并累加
3. 维护一个单调递减栈，栈中保存的是可能被左侧牛看到的牛的身高
4. 对于每头新牛，弹出栈中所有比它矮的牛（这些牛会被当前牛挡住）
5. 栈中剩余的牛的数量就是当前能看到当前这头牛的数量
6. 将当前牛压入栈中

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintN=8e4+10;// 最大牛的数量intn,x;// n:牛的数量，x:当前牛的身高intst[N],top=0;// st:模拟栈的数组，top:栈顶指针longlongans=0;// 存储最终结果intmain(){cin>>n;// 输入牛的数量for(inti=1;i<=n;i++){cin>>x;// 输入当前牛的身高（注意输入顺序是第1头到第N头，即从后向前）// 维护单调递减栈：弹出所有比当前牛矮的牛（它们会被当前牛挡住）while(top!=0&&x>=st[top])top--;// 栈中剩余的牛都是比当前牛高的，当前牛能看到这些牛ans+=top;// 将当前牛压入栈中st[++top]=x;}cout<<ans;// 输出总可见数return0;}

示例解析

以题目中的输入为例：

6 10 3 7 4 12 2

处理过程：

1. 第一头牛10：栈空，ans+=0，栈[10]
2. 第二头牛3：10>3，ans+=1，栈[10,3]
3. 第三头牛7：3<7被弹出，10>7，ans+=1，栈[10,7]
4. 第四头牛4：7>4，ans+=2，栈[10,7,4]
5. 第五头牛12：弹出4,7,10，栈空，ans+=0，栈[12]
6. 第六头牛2：12>2，ans+=1，栈[12,2]

最终ans=0+1+1+2+0+1=5，与样例输出一致。

六、经典题型解析：洛谷P5788 【模板】单调栈

题目描述：给定长度为n的整数序列，输出每个数之后第一个大于它的数的下标（从1开始计数）

输入样例：

5 1 4 2 3 5

输出样例：

2 5 4 5 0

解题思路

1. 维护单调递减栈（栈顶最小）
2. 逆序遍历数组（从右向左）
3. 如果当前元素 >= 栈顶元素时，持续弹出栈顶
4. 记录第一个大于当前元素的栈顶元素
5. 当前元素入栈

AC代码

#include<iostream>usingnamespacestd;constintMAXN=3e6+5;inta[MAXN],res[MAXN],stk[MAXN],top=0;intmain(){intn;cin>>n;for(inti=1;i<=n;++i)cin>>a[i];for(inti=n;i>=1;--i){while(top&&a[stk[top]]<=a[i])top--;// 弹出不符合条件的元素res[i]=top?stk[top]:0;// 记录结果stk[++top]=i;// 当前索引入栈}for(inti=1;i<=n;++i)cout<<res[i]<<" ";return0;}

执行过程图解（样例数据）

七、使用技巧总结

1. 遍历方向选择：取决于找左边还是右边的问题
2. 元素比较条件：严格单调（<）还是非严格单调（≤）
3. 结果记录时机：在元素出栈时记录或在入栈前记录
4. 栈内存储内容：根据需求存值、索引或结构体

更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}