考点：贪心

限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

• 源站时限：1 秒（牛客口径，非本题专属门槛）

解题思路

推荐方向：贪心

本题切入点

双向队列倒推：每一步都从首尾挑较小的数字放到结果尾部（若首尾相同需向里比较决定）。

每一步都取当前最优，靠问题性质保证局部最优能拼成全局最优。

思路框架（贪心 通法 · 非本题专属）

1. 找出「局部最优怎么选」（往往与排序后的顺序有关）。
2. 论证（或理性相信）这个贪心策略不会被反例击破：常用交换论证法。
3. 按策略一次扫描（通常要先排序）得到答案。
4. 若贪心无法证明，考虑改用 DP（贪心的反例通常来自「当前最优影响后续选择」）。

实现要点：贪心题关键在于排序规则：按什么关键字排序决定了策略是否正确。

复杂度：时间 O(n log n)（含排序） ｜ 空间 O(1) ~ O(n)

该范式的通法易错点

• 策略不成立却当成贪心做（典型错因）。
• 排序关键字选错，或相同关键字时的次级规则没考虑。

样例解读

样例 1：输入 6 / 0 2 3 1 2 1 → 输出 012123

第一次，原队列[2 3 1 2 1]，新队列[0];

第二次，原队列[2 3 1 2]，新队列[0 1];

第三次，原队列[2 3 1]，新队列[0 1 2];

第四次，原队列[2 3]，新队列[0 1 2 1];

第五次，原队列[3]，新队列[0 1 2 1 2];

第六次，原队列[ ]，新队列[0 1 2 1 2 3]。

最小数字位012123。