跳到主要内容

数组与区间

本节目标

围绕原地数组变换和有序区间边界，维护局部顺序与合并不变量。

数组题常要求在原地重排，区间题则要求保持边界有序。先明确修改对象和排序前提，再让每一步只维护一个清晰的不变量。

识别信号​

  • 题目要求在原数组中完成轮转、反转或重排；
  • 输入是一组端点区间，需要按位置合并；
  • 区间已经按左端点有序，且要插入一个新区间；
  • 只要当前区间与结果末尾的边界关系即可决定操作。

问题模型与核心不变量​

轮转中，三次翻转把“末尾移到开头”分解为整个数组和两个连续段的反转。区间处理中，结果列表始终保存已经处理完、按左端点排序且彼此不重叠的区间；当前区间只需与结果末尾比较。

通用模板​

按左端点排序
for interval in intervals:
    if answer 为空或 interval 与 answer 末尾不重叠:
        追加 interval
    else:
        扩展 answer 末尾的右端点

插入一个新区间时依次处理完全在左侧、与新区间重叠、完全在右侧的三段。

模板变体​

  • 原地轮转：整体翻转后分别翻转前 k 个和其余元素。
  • 合并区间：输入无序时先排序，再扫描合并。
  • 插入区间：输入已排序时不必重新排序，直接线性扫描。

母题序列​

按必学顺序完成下列两题：

  1. 轮转数组（必学）：用三次翻转实现 O(1) 额外空间轮转。
  2. 合并区间（必学）：排序后用结果末尾维护已合并边界。

常见误区​

  • 忘记先对 k 取模，轮转长度超过数组长度时越界。
  • 空数组直接对 k 取模，触发除零错误。
  • 把端点相接的区间当作不重叠，漏合并 [1,4] 与 [4,5]。
  • 插入区间时遗漏新区间左、右两侧尚未处理的区间。

迁移方向​

当区间还包含权重、选择数量或动态更新时，需要进一步建模为扫描线、贪心排序或数据结构维护；涉及二维坐标时可迁移到矩阵。