题目理解

我们有一个非递减排序的数组 $a$。
我们可以移除任意元素（包括不移除），然后按照规则将剩余元素分配到不同的数组中：

• 第一个元素 $a_1$ 总是开始一个新的数组；
• 对于 $i \ge 2$，如果 $a_{i-1} + 1 < a_i$，那么 $a_i$ 开始一个新数组；否则，$a_i$ 加入 $a_{i-1}$ 所在的数组。

目标：通过移除一些元素，使最终得到的数组个数最大。

关键观察

1. 第一个元素必须保留
   如果去掉 $a_1$，那么新的第一个元素 $a_j$（$j \ge 2$）的值只会更大或相等，不会让答案变好。保留 $a_1$ 可以尽早开始计数。

2. 跳跃规则
   规则本质是：
   若当前元素 $x$ 与上一个保留的元素 $last$ 满足：
   [ x - last > 1 ]
   则 $x$ 会开始一个新的数组。否则，它加入前一个数组。

3. 贪心策略
   我们希望在保留元素的过程中，尽可能多地触发“$x - last > 1$”的条件。
   因此，一旦某个元素与上一个保留元素的差大于 1，我们就保留它，并让它开始一个新数组。
   如果差 $\le 1$，我们可以选择跳过它，因为跳过它不会破坏后面的可能性，甚至可能让后面的元素更容易满足条件（例如跳过 $x+1$ 可以让 $x+2$ 相对上一个保留元素形成更大的差）。

4. 为什么跳过更小的差不会变差
   假设上一个保留元素是 $last$，当前元素是 $a_i = last + 1$。

   • 如果保留它，它会加入 $last$ 所在的数组，不增加数组数，且下一个可能元素是 $last+2$，差为 1，仍不满足 $>1$。
   • 如果跳过它，下一个元素 $a_{i+1} \ge last+2$，与 $last$ 的差 $\ge 2$，会触发新数组。
     因此跳过不会让答案变小。

算法步骤

1. 初始化 $last = -1$（因为 $a_i \ge 1$，所以 $-1$ 可以确保第一个元素一定满足条件）。
2. 初始化 $ans = 0$。
3. 遍历数组 $a$ 的每个元素 $x$：
   • 如果 $x - last > 1$：
     • 增加 $ans$（表示 $x$ 开始一个新数组）
     • 更新 $last = x$
   • 否则（$x - last \le 1$）：
     • 跳过 $x$（不更新 $last$，也不增加 $ans$）
4. 输出 $ans$。

示例验证

示例 1

$a = [1,2,3,4,5,6]$

• $x=1$：$1 - (-1) = 2 > 1$ → $ans=1, last=1$
• $x=2$：$2-1=1 \le 1$ → 跳过
• $x=3$：$3-1=2>1$ → $ans=2, last=3$
• $x=4$：$4-3=1\le1$ → 跳过
• $x=5$：$5-3=2>1$ → $ans=3, last=5$
• $x=6$：$6-5=1\le1$ → 跳过
  输出 $3$，与题目一致。

示例 3

$a = [1,2,2,4]$

• $x=1$：$ans=1, last=1$
• $x=2$：$2-1=1$ → 跳过
• $x=2$：$2-1=1$ → 跳过
• $x=4$：$4-1=3>1$ → $ans=2, last=4$
  输出 $2$，正确。

示例 5

$a = [1,4,8]$

• $x=1$：$ans=1, last=1$
• $x=4$：$4-1=3>1$ → $ans=2, last=4$
• $x=8$：$8-4=4>1$ → $ans=3, last=8$
  输出 $3$，正确。

复杂度分析

• 每个元素只处理一次，$O(n)$ 时间。
• 仅使用常数个变量，$O(1)$ 额外空间。
• 总 $n$ 不超过 $2 \times 10^5$，可轻松通过。

总结

题目的贪心策略是：
只要当前元素与上一个保留元素的差值大于 1，就保留它并增加数组计数；否则跳过它。
这样可以在保留第一个元素的基础上，最大化“新数组”的触发次数。