CJTX06｜删除数字 题解

核心算法

每次删除第一个“下降位置”前的较大数字；若整个字符串非递减，则删除末位。

思路推导

为了让结果尽可能小，最优先要让靠左的数字变小。扫描字符串，找到第一个满足 $s_i>s_{i+1}$ 的位置，删除 $s_i$，就能让更小的 $s_{i+1}$ 提前一位。若不存在下降位置，说明数字非递减，删除末尾最大（或并列最大）的数字影响最小。重复 $k$ 次。

正确性说明

设第一个下降位置为 $i$。在 $i$ 之前数字均非递减，删除其中更靠前且不大于后继的数字只会让一个不更小的数字提前；删除 $s_i$ 则第一次产生尽可能靠左的减小。十进制数的比较首先由更靠左的位置决定，因此本次选择最优。若不存在下降位置，删去越靠后的数字越晚影响结果，删除末位最优。对每次删除重复应用即可。

复杂度

• 时间复杂度：$O(k|S|)$，在本题范围内最多约 $2.5\times10^7$ 次字符比较；
• 空间复杂度：$O(|S|)$。

易错点

• 不能把输入转成整数；
• 找不到下降位置时要删除末位；
• 必须恰好删除 $k$ 位；
• 输出前要去掉前导零，但结果为空或全零时输出 0。