🥈Medium
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:
- num 的长度小于 10002 且 ≥ k。
- num 不会包含任何前导零。
示例 1 :
输入: num = "1432219", k = 3输出: "1219"解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例 2 :
输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 :
输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0
题解
这道题费了半天功夫，结果发现移掉的K个数不是连续的，😒，唉！！
贪心+单调栈
对于两个长度相同的数字序列，最左边数字的大小将会决定整个序列的大小，比如说
，
。如果
，则
。
所以，要想使剩下的数字最小，需要保证靠左的数字尽可能小。基于这些分析，可以得出“删除一个数字”的贪心策略：
给定一个长度为n的序列
，从左向右找到第
（
）个位置使得
，并删去
，如果没找到这样的
，则说明整个序列是单调不降的（例如87554333），删除最后一个字符即可。
所以，可以每次对数字序列执行这一策略，删除一个字符后，后续的
个序列就变成了新的子问题，然后继续使用同样的策略，直到删除
次。
但这样暴力的实现，复杂度会变成
，需要对算法进行优化。
因为是从左向右构造答案。可以用栈来维护当前的答案序列，栈中的元素代表截止到当前位置，删除不超过次个数字后，所能得到的整数。而且在使用个删除次数之前，栈中的序列从栈底到栈顶单调不降。
因此，对每个数字，如果该数字小于栈顶元素，就不断弹出栈顶元素，直到：
- 栈为空
- 新的栈顶元素不大于当前数字
- 已经删除了k位数字
若有收获，就点个赞吧
0 人点赞
