单调栈 & 单调队列 入门题单
本题单涵盖了比较丰富的单调栈或单调队列的入门题,包括些许模板,很适合练手,也考验部分思维。
难度大概介于黄到蓝之间。
各个题目的大致做法/思路
- P5788:单调栈模板题。
- P1886:单调队列模板题。
- B3666:单调栈偏模板题。
- AT_abc359_e:单调栈,带小部分思维。
- P6503:需使用两个单调栈(一个正序一个倒序),需要一部分思维推导。
- AT_agc005_b:与上一题类似,稍微简单一些,只需一个单调栈,也需思维推导。
- CF817D:与 P6503 几乎完全相同,双倍经验。
- P1725:经典单调队列优化 DP 好题。
- P4147:巧用思维的单调栈好题,一开始需计算前缀和数组,稍后对前缀和数组进行两次单调栈;同时运用单调栈中的经典思想,如果题目中出现取最大值/最小值时,自行标定某数为最大值/最小值,然后左右扩张。
- CF547B:运用单调栈经典思想,用两个单调栈对每个点进行维护并计算答案。
- CF5E:单调栈好题,破环成链有巧招,后面就是普通单调栈了,注意细节即可。
- AT_abc194_e:滑动窗口做法,也是单调队列的偏板子题,移动时用桶维护并对应更新答案。
- B3667:单调队列偏模板题。
- P2422:运用单调栈经典思想维护两个数组并分别计算答案。
- CF1077F2:典型的单调队列优化 DP,设计动态规划状态以及转移,但是会超时,因此在转移部分进行单调队列优化。
- P2216:单调队列好题,先分别维护行和列,运用经典思想然后对应计算答案。
- P2698:二分题,
check 函数的思想是简单单调队列。
- CF1237D:单调队列好题,需破环为链而且得开三倍,后面维护单调队列即可,注意细节。
- CF487B:单调队列优化 DP,中间的优化过程需要部分思维。
- CF940E:动态规划题,前面需要用单调队列预处理辅助数组。
相信这份题单能帮助刚学或复习单调栈 & 单调队列的各位 OIers 提供帮助!