超时反例与退化输入设计¶

目标：学会主动构造最坏输入，而不是只用官方样例自我感觉良好。

一、为什么要刻意设计退化输入¶

很多错误解法并不是逻辑错，而是在：

• 大规模下超时
• 极端分布下退化
• 重复值或单调序列下失效
• 高频更新下复杂度爆炸

这类问题正是线上评测和面试区分度的来源。

二、常见退化输入模板¶

1. 单调序列¶

适合打掉：

• 单调栈边界写错
• 双指针错误剪枝
• 递增/递减假设不成立

2. 全重复或大量重复¶

适合打掉：

• 哈希计数边界
• 去重逻辑
• 排序后双指针重复跳过错误

3. 极大窗口 / 极大子数组¶

适合打掉：

• 滑动窗口重复扫描
• 前缀和边界问题

4. 稀疏图 / 稠密图¶

适合打掉：

• 图算法复杂度判断错误
• 邻接矩阵与邻接表误用

三、超时反例怎么写¶

推荐模板：

错误解法：每个窗口都重新遍历 k 个元素，复杂度 O(nk)
退化输入：n = 100000, k = 50000
结果：比较次数约 5e9，无法通过评测
正确方向：单调队列，把复杂度降到 O(n)

四、你自己的题解至少要保留什么¶

• 1 个边界输入
• 1 个退化输入
• 1 个压力输入
• 1 个容易误导人的反例

这也是后面补齐 OJ 高质量测试点时最应该优先补的四类。