这是一个创建于 546 天前的主题，其中的信息可能已经有所发展或是发生改变。
这道题目的解法是 每次删除一个字符，使剩下的字符最小。然后执行 k 次。
这道题目为什么贪心算法是最优解？怎么证明。
 |
1
JasonLaw 2023-05-30 16:24:14 +08:00
题目链接： https://leetcode.com/problems/remove-k-digits/
Greedy? 不应该是 Monotonic Stack 吗？ 你应该把你的 solution 发出来，这样子才能有正确性的证明，建议你 append 一下。 |
|
2
JasonLaw 2023-05-30 16:24:41 +08:00
NeetCode 的讲解。
|
 |
3
cpstar 2023-05-30 17:15:43 +08:00
看视频理解了题目，但是不赞同在数字大小上做文章，相反，直接干枚举。
我感觉，应该是，在 num （ m 长）中取 m-k 个数字，然后求最小？ 有啥问题？ |
 |
4
kayleh 2023-05-31 03:19:15 +08:00 via Android
1. 只能移除数字，数字的原本顺序无法改变，所以 1432219 移除 3 位的有效答案只能是 1219 ，而不是 1123 。所以只能顺序遍历构造答案。
2. 组成最小数字的数位应该是递增的(单调栈) 3. 优先从左到右构造数字(尽量让高位的数较小)对答案贡献越大(贪心) |
Select Language