题目重点：题目给 [0,0,0]、k=1 得 3；排序各项后选区间内最小未用整数，解释为何一般无序输入需排序。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 每个元素独立选一个整数 x_i∈[a_i−k,a_i+k]，k 为非负整数，目标最大化不同 x_i 的个数；重复赋值允许但不增加答案。
- 输入一般无序，整数比较不溢出；训练版对 a_i 排序。若题目保证已按 a_i 排序，可去掉排序得到 O(n)。
- 只求最大不同值数，也可输出选中的不同值作为证据；没被匹配到独特值的元素仍可任选区间内一个值。
解题路线
- 每个 a_i 对应整数区间 [a_i−k,a_i+k]；按 a_i 从小到大排序，因 k 相同，区间左右端点也同序。
- 维护 last 为上一个已分配的不同整数。当前区间取 candidate=max(a_i−k,last+1)；若 candidate≤a_i+k，就给此元素一个新值并更新 last/count；否则它无法在不牺牲前面选择的情况下增加不同值。
- 交换论证：对当前区间任何可行新值 y≥candidate，选更小的 candidate 留给所有后续区间至少一样多的右侧整数，因此不会减少未来最优数。按右端点递增处理区间，与经典区间到点匹配一致。
- 检验 [0,0,0],k=1：依次选 −1、0、1，得 3；检验 [0,0,0,0] 则最多 3。负数、k=0、宽间隔以及有序/无序都要测。
- 若有人声称一般 O(n)，先澄清输入已排序或值域可线性桶排序；无约束比较排序版为 O(n log n)，不能把排序成本藏起来。
手动走一遍
a=[2,0,0],k=1，排序为 [0,0,2]：前两项选 −1、0；第三项区间 [1,3] 选 1，答案 3。若贪心先处理 a=2 并取其左端 1，再处理两个 0 仍可能成功，但无序任意局部次序不能直接继承交换证明。
规模与取舍
一般输入排序 O(n log n) 时间，扫描 O(n) 时间；若原地排序额外 O(1) 或排序实现所需空间，输出选择 O(n)。已排序输入 O(n) 时间、O(1) 计数空间。
易错点与追问
容易失分的边界
- 把每项只能加或只能减 k，漏掉区间中间值 0。
- 给同一个整数分配多项仍计多次。
- 对一般无序输入直接宣称 O(n) 而没说明排序/值域假设。
- candidate 超出右端点时强行分配，违反每项允许范围。
继续深挖
- 若每项有不同 k_i，按什么端点排序？
- 若整数范围有禁止点，如何修改？
- 如何输出实际每项选择而不只计数？
- 若输入已排序，能否流式处理？
