数组与矩阵综合
本节目标
在基础模板上增加状态同步、候选淘汰和原地编码，完成数组与矩阵压轴母题。
综合题并不要求一套全新的高级算法。它们通常在基础模型上多加一层状态或证明责任：双指针需要证明何时能结算贡献，滑动窗口需要同步多类计数，原地算法需要同时保留旧状态和写入新状态。
识别信号
下面这些特征说明题目已经从基础模板进入综合应用：
- 左右两侧共同决定当前位置的贡献；
- 窗口合法性由多种字符及其需求次数共同决定；
- 候选会过期，需要在移动窗口时及时淘汰；
- 值域与数组下标存在对应关系，可以把数组自身当作哈希表；
- 所有位置必须根据同一时刻的旧状态同步更新；
- 新区间与有序无交集区间之间存在明确的左、中、右三段。
问题模型与核心不变量
六道题分别增加一项关键不变量：
- 接雨水：较低一侧的最高边界已经足以确定该位置的积水；
- 最小覆盖子串：
formed精确统计已经满足需求频次的字符种类； - 滑动窗口最大值：队列只保存仍在窗口内、且可能成为最大值的下标；
- 缺失的第一个正数：值
x应被放到下标x - 1； - 生命游戏：编码后的格子仍能恢复其旧状态；
- 插入区间：扫描过程严格分成新区间左侧、重叠区和右侧。
通用模板
综合题仍然遵循“先定义状态，再规定更新顺序”：
确定基础模型和必须维护的状态
写出每个状态代表的精确含义
规定加入、删除、结算或编码的顺序
证明一次移动至少排除一个不再需要的候选
最后统一还原答案或新状态
如果无法用一句话解释某个变量的含义，就不应急着写循环。
模板变体
- 双向贡献可以从较低边界结算，也可以用单调结构等待更高边界出现。
- 复杂窗口既能维护满足种类数，也能维护缺失字符总数；本章只保留一套主实现。
- 单调候选既可维护最大值，也可反向维护最小值。
- 原地索引放置适用于值域接近
[1, n]的题目；值域过大时应改用哈希集合。 - 多状态编码可以使用额外整数状态，也可以在数值允许时用位来保存旧值与新值。
母题序列
以下题目按拓展顺序学习：
这六题分别对应双向贡献、复杂窗口状态、单调候选、原地哈希、原地状态编码和区间三段扫描。
常见误区
- 只记住最终代码，不知道一个候选在何时已经可以安全结算或删除。
- 更新答案后忘记同步窗口频次、满足种类数或队列下标。
- 原地放置相同值时不断交换，造成死循环。
- 状态编码后直接按新值统计邻居，破坏同步更新语义。
- 插入区间时边扫描边随意修改结果末尾，没有明确三段边界。
迁移方向
完成本节后，应该能够把复杂题拆回基础框架：
- 双向贡献回到双指针；
- 多类计数回到滑动窗口；
- 过期候选回到队列维护；
- 值与下标映射回到数组原地存储；
- 同步更新回到状态编码；
- 区间插入回到排序区间扫描。
未来遇到更难的题，先寻找它复用了哪个基础模型，再单独处理新增状态。这样比为每道压轴题记忆一份孤立代码更可靠。