删除k个数字:后，使得到的数字尽可能的小贪心思想

删除k个数字之后，使得到的数字尽可能的小

参考题目：洛谷P1106

问题：2135624 这么一串数字，删除两个数字，怎么使删除后得到的数字尽可能的小？

解法： 每次删除第一个大于后一位数的数（贪心思想）

操作过程：

注意点：

1. 每次删除操作结束后，剩下的数字需要重新合并变成一个新的数字
2. 如果每次都是删除最大的那个数字，不可取，因为重新合并后应当注意数字位数的问题
3. 删除数字的位置优先级要大于数字本身的大小

怎么实现？

方案一：

1. List item

2. 使用二重循环，外层为 k 的大小，内层为数字长度

3. 找到符合要求的数字删除后，将剩下的数字合并到一起，C 中使用类直接进行 运算

4. 最后输出最终的结果

缺陷：

• substr() 方法实现的原理是将引用的子串复制一份，这个时候会产生额外的空间，而且多进行了一个遍历子串的操作
• 使用二层循环，k 做外层的时候，每一次删除都要遍历整个数字，其实没有必要，每一次删除之后，下一个将要被删除的数字一定是在当前被删除这个数字的后面，因为每次删除的数字都会是第一个大于后一位数的数字

方案二：（改进方案一）

1. 使用一层循环，也就是遍历一次整个数组
2. 借助栈
3. 遍历数组的时候，将每次遍历的数字入栈
4. 在 k > 0 的时候将栈顶的元素和数组的下一位数进行对比，例如当前是下标为 1 的元素入栈，这个元素就会在栈顶，这个时候将栈顶元素和下标为 2 的元素对比，也就是实现了相邻两个的数字进行对比
5. 如果栈顶元素大于数组当前下标的下一个元素，将栈顶元素出栈，
6. 栈中剩下的元素就是最终结果的倒序

为什么是栈？

1. 栈的特点： 后进先出
2. 根据上述特点，可以保证每次进入的元素一定是距离待判断元素最近的那一个

为什么是贪心思想？

1. 影响删除后的结果的因素有两个，一个是删除元素所处的位置，另一个是删除元素的大小，显然，应该是删除位数较高，而且数字较大的那个，经过每一次的验证发现，结果符合要求，贪心成立

需要注意的点：

1. 只关注删除元素所处位置，即每次删除最高位的数字，可能会导致结果不一定是最小的，比如最高位是 1 ，他的后一位是 9 ，这就会导致结果不是最优
2. 只关注删除元素的大小，不关注删除元素的位置，可能会导致上一条一样的结果，比如 1 在最高位而 9 在个位（最后一位）上，删除 9 之后得到的结果不一定是最优解
3. 所以，应该结合数字的大小和数字的位置两种情况的考虑

这篇好文章是转载于：学新通技术网