企业官网建设流程全解析

公众号可以做网站维护链接吗,设计平台市场分析,wordpress 子菜单项,红色网站欣赏信奥赛C提高组csp-s之单调栈详解 一、单调栈核心概念 单调栈是一种特殊的栈结构#xff0c;栈内元素始终保持单调递增或递减的顺序。核心应用场景#xff1a;快速寻找序列中每个元素左/右侧第一个比它大#xff08;或小#xff09;的元素。 时间复杂度#xff1a;O(n)提高组csp-s之单调栈详解一、单调栈核心概念单调栈是一种特殊的栈结构栈内元素始终保持单调递增或递减的顺序。核心应用场景快速寻找序列中每个元素左/右侧第一个比它大或小的元素。时间复杂度O(n)每个元素至多入栈、出栈一次二、数组模拟栈的优势执行效率高于STL的stack容器内存连续访问缓存命中率高更适合算法竞赛的严苛性能要求// 数组模拟栈通用写法constintMAXN3e65;intstk[MAXN],top0;// 栈和栈顶指针// 入栈操作stk[top]value;// 出栈操作top--;三、案例1找左侧第1个比当前元素小的元素题目描述给定长度为n的正整数序列输出每个数之前第一个小于它的数如果没有输出0**数据规模**n≤10 6 10^6106输入样例5 1 4 2 3 5输出样例0 1 1 2 3解题思路维护单调递增栈栈顶最大正序遍历数组从左向右如果当前元素 ≤栈顶元素时持续弹出栈顶记录第一个小于当前元素的栈顶元素当前元素入栈AC代码#includeiostreamusingnamespacestd;constintN1e610;// 定义常量N作为栈的最大可能大小intn,x;// n: 序列长度; x: 当前读取的数值intst[N],top0;// st: 模拟栈的数组; top: 栈顶指针初始为0intmain(){cinn;// 读取序列长度nfor(inti1;in;i){// 遍历序列中的每个元素cinx;// 读取当前元素x// 维护单调栈弹出栈顶所有大于等于x的元素while(top!0xst[top]){top--;}// 如果栈为空说明前面没有比x小的数输出0if(top0){cout0 ;}// 否则栈顶元素就是x之前第一个比它小的数else{coutst[top] ;}// 将当前元素x压入栈中st[top]x;}return0;}算法思路单调栈维护一个栈栈中元素始终保持单调递增的顺序。对于当前元素x从栈顶开始弹出所有大于等于x的元素。这样做的目的是确保栈中剩下的元素都比x小且栈顶是离x最近的比它小的数。如果栈为空说明前面没有比x小的数输出0否则输出栈顶元素。最后将x压入栈中继续处理下一个数。时间复杂度每个元素最多入栈和出栈一次因此时间复杂度为O(n)能够高效处理大规模数据n ≤ 1e6。关键点单调栈的性质栈内元素始终单调递增可以快速找到第一个比当前数小的数。栈的操作弹出操作移除无效元素大于等于当前数的元素。输出结果栈顶元素或0。压入操作将当前数加入栈中维护单调性。示例流程以输入1 4 2 3 5为例1栈空 → 输出0栈[1]4栈顶14→ 输出1栈[1, 4]2弹出44 2栈顶12→ 输出1栈[1, 2]3栈顶23→ 输出2栈[1, 2, 3]5栈顶35→ 输出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解题思路维护单调递减栈栈顶最小逆序遍历数组从右往左如果当前元素 ≥栈顶元素时持续弹出栈顶记录第一个大于当前元素的栈顶元素当前元素入栈代码实现#includeiostreamusingnamespacestd;constintN1e610;// 定义常量N为数组的最大长度intn,a[N];// n为序列长度a数组存储输入的序列intst[N],top0;// st数组模拟栈top为栈顶指针intres[N];// res数组存储结果intmain(){cinn;// 输入序列长度nfor(inti1;in;i)cina[i];// 输入序列// 从后往前遍历序列for(intin;i1;i--){// 维护单调栈弹出栈顶所有小于等于当前元素的元素while(top!0a[i]st[top]){top--;}// 如果栈为空说明当前元素之后没有比它大的数结果为0if(top0){res[i]0;}// 否则栈顶元素就是当前元素之后第一个比它大的数else{res[i]st[top];}// 将当前元素压入栈中st[top]a[i];}// 输出结果for(inti1;in;i){coutres[i] ;}return0;}算法思路单调栈使用单调栈来高效地找到每个元素之后第一个比它大的元素。栈中维护的是一个单调递减的序列。逆向遍历从后往前遍历数组这样可以保证栈中保存的是当前元素之后的元素且栈顶是离当前元素最近的元素。栈操作对于当前元素弹出栈中所有小于或等于它的元素。因为这些元素不可能成为前面元素的目标当前元素比它们大且更靠前。如果栈为空说明当前元素之后没有比它大的元素结果为0。否则栈顶元素就是当前元素之后第一个比它大的元素。将当前元素压入栈中。输出结果正向遍历结果数组并输出。时间复杂度O(n)。每个元素最多入栈和出栈一次因此总的时间复杂度是线性的。示例演示以输入样例1 4 2 3 5为例初始化i 5a[5] 5栈为空res[5] 0栈变为[5]。i 4a[4] 3栈顶5 3res[4] 5栈变为[5, 3]。i 3a[3] 2栈顶3 2res[3] 3栈变为[5, 3, 2]。i 2a[2] 4弹出2和3因为4 2和4 3栈顶5 4res[2] 5栈变为[5, 4]。i 1a[1] 1栈顶4 1res[1] 4栈变为[5, 4, 1]。最终结果数组为[4, 5, 3, 5, 0]。五、经典题型解析洛谷P2866 [USACO06NOV] Bad Hair Day S思路分析搞清楚方向第1头牛在最后面左第n头牛在最前面右问题转化为计算每头牛能被左侧的多少头牛看到并累加维护一个单调递减栈栈中保存的是可能被左侧牛看到的牛的身高对于每头新牛弹出栈中所有比它矮的牛这些牛会被当前牛挡住栈中剩余的牛的数量就是当前能看到当前这头牛的数量将当前牛压入栈中代码实现#includebits/stdc.husingnamespacestd;constintN8e410;// 最大牛的数量intn,x;// n:牛的数量x:当前牛的身高intst[N],top0;// st:模拟栈的数组top:栈顶指针longlongans0;// 存储最终结果intmain(){cinn;// 输入牛的数量for(inti1;in;i){cinx;// 输入当前牛的身高注意输入顺序是第1头到第N头即从后向前// 维护单调递减栈弹出所有比当前牛矮的牛它们会被当前牛挡住while(top!0xst[top])top--;// 栈中剩余的牛都是比当前牛高的当前牛能看到这些牛anstop;// 将当前牛压入栈中st[top]x;}coutans;// 输出总可见数return0;}示例解析以题目中的输入为例6 10 3 7 4 12 2处理过程第一头牛10栈空ans0栈[10]第二头牛3103ans1栈[10,3]第三头牛737被弹出107ans1栈[10,7]第四头牛474ans2栈[10,7,4]第五头牛12弹出4,7,10栈空ans0栈[12]第六头牛2122ans1栈[12,2]最终ans0112015与样例输出一致。六、经典题型解析洛谷P5788 【模板】单调栈题目描述给定长度为n的整数序列输出每个数之后第一个大于它的数的下标从1开始计数输入样例5 1 4 2 3 5输出样例2 5 4 5 0解题思路维护单调递减栈栈顶最小逆序遍历数组从右向左如果当前元素 栈顶元素时持续弹出栈顶记录第一个大于当前元素的栈顶元素当前元素入栈AC代码#includeiostreamusingnamespacestd;constintMAXN3e65;inta[MAXN],res[MAXN],stk[MAXN],top0;intmain(){intn;cinn;for(inti1;in;i)cina[i];for(intin;i1;--i){while(topa[stk[top]]a[i])top--;// 弹出不符合条件的元素res[i]top?stk[top]:0;// 记录结果stk[top]i;// 当前索引入栈}for(inti1;in;i)coutres[i] ;return0;}执行过程图解样例数据当前ia[i]栈状态底→顶操作res[i]55空入栈043[5]35532[5,4]23424[5,4,3]弹出3,4→42511[5,2]142七、使用技巧总结遍历方向选择取决于找左边还是右边的问题元素比较条件严格单调还是非严格单调≤结果记录时机在元素出栈时记录或在入栈前记录栈内存储内容根据需求存值、索引或结构体更多系列知识请查看专栏《信奥赛C提高组csp-s知识详解及案例实践》https://blog.csdn.net/weixin_66461496/category_13113932.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、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.html4、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}