通用算法高频模式索引

图：依赖图帮助识别状态转移、共享子问题和可复用的中间结果。 来源：Dependency graph，作者 Aston Zhang、Zachary C. Lipton、Mu Li、Alexander J. Smola（D2L.ai），许可 CC BY-SA 4.0。

识别信号

连续子数组与约束单调变化优先检查滑动窗口；有序空间和“是否可行”单调性检查二分；局部最优反复弹出使用堆；连通性动态合并考虑并查集；状态由更小子问题复用时检查动态规划。

核心思路

不要背题目答案。为每种模式写出循环不变量：窗口中始终满足什么，二分区间哪一侧已被排除，DFS 返回值代表什么，DP 状态包含哪些决策信息。

实现模板

def lower_bound(values, target):
    left, right = 0, len(values)
    while left < right:
        mid = left + (right - left) // 2
        if values[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

复杂度

二分查找时间 O(log n)、额外空间 O(1)。复杂度必须按数据结构操作计算；堆操作不是常数，递归还要计入调用栈。

边界条件

重点覆盖空输入、单元素、全部相同、答案不存在、整数溢出、图中环、重复访问和递归深度。

常见变体

• 二分答案：将优化问题转成单调可行性判断。
• 单调栈/队列：维护尚未解决的候选或窗口极值。
• 多源 BFS：把所有起点同时入队。
• 区间 DP：状态由区间长度和分割点决定。

测试用例

对 lower_bound 测试 []、[1]、[1,1,1]、目标小于最小值、位于中间和大于最大值，并核对返回插入位置。