河北大学2022寒假萌新程序设计训练每日知识分享-day27
每日分享——单调栈&单调队列
1.核心思想
利用栈和队列的单调性质,优化枚举区间内极值O(n)的时间复杂度到O(1)
2. 问题特征
(1)区间内的极值(最大值,最小值)
(2)找当前数左(右)边第一个比当前数大(小)的数
3. 分析流程
step1: 先利用普通栈(队列)给出解法
step2: 删除冗余的元素,得到具有单调性的栈和队列
step3: 优化枚举元素的O(n)的时间复杂度到O(1)
4. 代码模板
1 | 单调栈: |
河北大学2022寒假萌新程序设计训练每日知识分享-day27
利用栈和队列的单调性质,优化枚举区间内极值O(n)的时间复杂度到O(1)
(1)区间内的极值(最大值,最小值)
(2)找当前数左(右)边第一个比当前数大(小)的数
step1: 先利用普通栈(队列)给出解法
step2: 删除冗余的元素,得到具有单调性的栈和队列
step3: 优化枚举元素的O(n)的时间复杂度到O(1)
1 | 单调栈: |