单调栈保持栈内元素单调递增或递减，高效解决「下一个更大/小元素」类问题。

单调栈类型

KMP 算法利用已匹配信息避免从头搜索，时间复杂度 O(n+m)，远优于暴力搜索的 O(n×m)。

核心思想

当发生不匹配时，利用部分匹配表（next 数组） 决定模式串移动距离，而非重新开始比较。

next 数组构建

next[i] …

并查集（Union-Find）是处理动态连通性问题的高效数据结构，通过路径压缩和按秩合并，Find 和 Union 操作可达近乎 O(1) 时间复杂度。

核心概念

并查集管理若干不相交集合，支持两个核心操作：

• Find：查找元素所属集 …

单调栈是特殊栈结构，栈中元素保持单调递增或递减，用于快速查找下一个更大/更小元素。

核心特点

• 单调递增栈：栈底到栈顶逐渐增大
• 单调递减栈：栈底到栈顶逐渐减小

典型应用

代码风格统一提升可读性，刷题需区分 ACM 模式与核心代码模式的输入输出处理。

代码风格规范

• 变量命名：驼峰命名法
• Python 规范：遵循 PEP8

刷题模式对比

bisect 模块提供二分查找算法，用于在有序序列中快速查找插入位置，时间复杂度 O(log n)。

核心函数