【漫画算法】删除k个数字后最小

算法】删除k个数字后最小"/>

【漫画算法】删除k个数字后最小

问题描述

给出一个整数， 从该整数中去掉k个数字， 要求剩下的数字形成的新整数尽可能
小。 应该如何选取被去掉的数字？

分析

为了剩下的数字组成的数尽可能小，我们应对尽可能在高位进行删减。

不同的顺序对数字的影响不同：

12345，13245我们删掉1和删掉3，得到的结果是2345，1245显然后者会更小。

产生逆序的位置的数字删减，对源数据的大小影响更大。

示例

541 270 936 删减3个数字，使得结果最小。

第一次，删掉5.

此处为什么删除5？为什么不是4？

如果删掉4，结果是51270936，依然很大。高位对数字的影响比低位更大一些。

那假如原数是451270936呢？删除4还是5？

删除4结果是51270936，删除5结果是41270936，显然删除5的结果更小，这是因为4和5没有产生逆序，删除4结果反而较大。

第二次，删除4

 第三次，删除7

 代码实现

在代码实现上，倾向于使用栈实现。

public String removeKDigits(String num, int k) {//新整数的最终长度 = 原整数长度-kint newLength = num.length() - k;//创建一个栈， 用于接收所有的数字char[] stack = new char[num.length()];int top = 0;for (int i = 0; i < num.length(); ++i) {//遍历当前数字char c = num.charAt(i);//当栈顶数字大于遍历到的当前数字时， 栈顶数字出栈（ 相当于删除数字）while (top > 0 && stack[top-1] > c && k > 0) {top -= 1;k -= 1;}//遍历到的当前数字入栈stack[top++] = c;}// 找到栈中第1个非零数字的位置， 以此构建新的整数字符串int offset = 0;while (offset < newLength && stack[offset] == '0') {offset++;}return offset == newLength? "0": new String(stack, offset, newLength - offset);
}

依次从高位入栈，判断当前元素和栈顶元素的相当大小，如果大于栈顶元素则进栈，否则栈顶元素弹栈后再压栈。

 当前没有元素，直接压栈。

出现逆序，先弹栈再压栈。（第一次删除）

出现逆序， 先弹栈再压栈。（第二次删除）

 没有逆序，直接压栈。

 出现逆序， 先弹栈再压栈。（第三次删除，删除完毕）

 删除完毕，其他元素不再比较，直接压栈。