版权信息：

说明

键盘输入一个高精度的正整数n（n ≤ 1000位），去掉其中任意s个数字后剩下的数字按原左右顺序将组成一个新的正整数。编程对给定的n和s（s < n的位数，且数据保证n删除s个数之后不为0，还是一个非0的整数），寻找一种方案，使得剩下的数字组成的数最小。

例如：153748要删除2个数，使得剩下的数字最小，应当删除5和7，得到1348。（注意：1087如果要删除1个数，删除1结果是最小的，得到结果87）

输入格式

第一行是一个高精度整数n 第二行是需要删除的位数s

输出格式

最后剩下的最小数

样例

153748
2

1348

算法分析

1. 目标： 通过删除s个数字，最终使剩下的数字组合成最小的可能值。
2. 思路：
   • 采用贪心策略，尽量删除较大的数字，并且保留较小的数字。
   • 使用栈（stack）结构来帮助实现这一贪心选择。我们可以从左到右遍历数字：
     • 如果当前数字小于栈顶元素，可以删除栈顶元素，继续尝试删除。
     • 每次删除一个数字，剩余的数字将变得更小。
     • 当栈中保留的数字满足需求时，停止删除。
3. 具体步骤：
   • 遍历数字，如果栈顶的数字比当前数字大且还可以删除更多数字，就弹出栈顶元素。
   • 如果当前数字无法继续删除，直接将其入栈。
   • 最后栈中的数字就是剩下的最小数。
4. 优化：
   • 使用栈结构，逐步构建最小的数字。
   • 确保删除数字的顺序符合贪心策略。

时间复杂度分析