B. 数组修复 详细题解

题目核心理解

给定一个长度为 $n$ 的整数数组 $a$。 你可以执行任意次操作：将一个大于等于 $10$ 的数，替换为它的各位数字（顺序不变）。 问是否可以通过若干次操作，使得数组变为非递减有序，即满足 $a_1\le a_2\le\dots\le a_k$。

核心思路

1. 关键性质

• 如果出现 $a_i > a_{i+1}$，那么 $a_i$ 必须拆分，因为只有拆分才能让它变小。
• 拆分后的数字序列本身也必须是非递减的，例如 $98$ 拆分为 $9,8$ 就不合法。
• 最优策略是从右向左贪心处理，尽可能不拆分，只在必须拆分时才拆。

2. 贪心规则

从右往左遍历数组，维护一个已处理的数字序列：

• 如果当前数字 大于 已处理序列的最后一个数字 → 必须拆分，并将各位加入序列。
• 否则 → 不拆分，直接将该数字加入序列。

3. 最终检查

贪心构造完后，必须整体检查是否非递减：

• 像 $98$ 这类数字拆分后本身递减，必须额外验证。
• 维护的序列恰好是最终数组的逆序，反转后即可直接检查。

算法流程

1. 从右向左遍历原数组。
2. 维护一个结果列表，根据大小关系决定是否拆分当前数字。
3. 拆分时按数字的高位到低位取出，并逆序加入列表。
4. 遍历完成后，反转列表得到最终构造的数组。
5. 检查是否非递减，合法输出 YES，否则 NO。

公式与复杂度分析

拆分触发条件：

最终合法性判断：

复杂度

• 每组测试用例时间复杂度：$O(n)$。
• 总复杂度：$O(t\cdot n)$。
• 可轻松处理 $t\le 10^3$、$n\le 50$ 的数据范围。