P2652. 找最小数

解题思路

注意，本题和 移掉K位数字 完全一致。

对于两个相同长度的数字序列，最左边不同的数字决定了这两个数字的大小。 例如，对于两个五位数，A = 1axxx，B = 1bxxx，如果 a > b 则存在 A > B。

贪心思想

贪心地思考这个问题，为了使得剩下的数字尽可能地小，我们肯定希望位于前面的大的数字被尽量删掉。 换句话说，若要使得剩下的数字最小，需要保证靠前的数字尽可能小。

单调栈的应用

假设我们从左到右正序遍历原数字（字符串形式）中的每一个数字字符 ch，如果当前字符比之前遍历过遇到的字符更小，则之前遇到过的字符应该被当前这个更小的字符顶替。 这些之前遇到过的更大字符，显然可以用单调栈来储存。即如下代码：

控制删除次数

同时，由于题目规定了最多删除的次数 n，因此我们还需要控制删除的次数。 可以需要构建一个变量 rest_n，来表示还剩下多少次可以进行的删除操作。

因此，出栈条件除了常规的 len(stack) 和 ch < stack[-1]，还要再加上一条 rest_n > 0。 同时，一旦进入出栈的 while 循环，就得进行 rest_n 的递减，表示消耗了一次删除的机会。

故整个单调栈算法的核心代码为：

最终结果处理

注意到，删除了 n 次后的数字长度一定为 len(NUM1) - n，但是单调栈中最终的元素长度并不一定是 len(NUM1) - n，即 n 次删除机会没有用完，rest_n 在退出 for 循环之后没有降为 0（譬如示例二）。 故最终单调栈中的有效数字仅为前 len(NUM1) - n 个元素，最终取 stack[:len(NUM1) - n] 作为答案。

复杂度分析 设数字字符串 NUM1 的长度为 m，允许删除的位数为 n。

• 时间复杂度：O(m)。for 循环把每个字符恰好处理一次；内层 while 虽然嵌套，但每个字符至多入栈一次，入栈后至多被弹出一次（弹出还要消耗一次删除机会），所以弹栈在整个程序中的总次数不超过 min(m, n)，两层循环的总工作量是摊还线性的。最后取 stack[:len(NUM1)-n] 并 join 成字符串也只是 O(m)。
• 空间复杂度：O(m)。最坏情况（数字整体不降，或删除机会很早用完）栈会保留几乎全部字符。

瓶颈就在这一趟带弹栈的遍历上，没有排序或额外的嵌套扫描；rest_n 的控制只增加常数开销。