本题来自@陈利人 微信公众账户：待字闺中
原题
对于一个n位正整数a,去掉其中任意k(k<=n)个数字后，剩下的数字按原次序排列可以组成一个新的正整数。设计一个删除算法，使得剩下的数字组成的正整数最小。
例如，a=13243221，k=5，输出：121
对于题目中的例子，数字13243221，删除5个数字之后，使得剩下的几个数字组成的整数最小。先考虑简单的解决办法：
当k=1时，如果要删除13243221中的一个数字使得剩下的几个数字组成的整数最小，很显然，应该删除第二位数字3，这样剩下的整数为1243321
对于1243321整数1243321，当k=1时，要使剩下的整数最小，那么应该删除数字4，这样剩下的整数为123321
对于整数123321，当k=1时，要使剩下的整数最小，那么应该删除一个数字3，剩下的整数为12321
从上面的分析可以发现，对于k=1，如果所给定的整数的数字从左到右时升序，那么应该删除最右边的一个数，剩下的数字组成的整数最小，如果所给定的整数的数字从左到右为降序，那么应该删除最左边的数字使得剩下的数字所组成的整数最小。例如k=1时，整数123，应该删除最右边的3，所得的整数最小，又如k=1时，整数321，那么应该删除最左边的3，所得的整数最小。
那么k>1时，只需重复上面的步骤，直至k=0。
所以，对于整数a，删除k个数字后使所得整数最小的算法如下：
1.从左到右扫描整数a，比较相邻的位的数字a[i]与a[i+1]的大小；
2.若a[i] < a[i+1]，那么i++，直到a[i] >= a[i+1]或者到达整数最右边；
3.删除a[i]，k--，若k > 0则重复步骤1。
对应算法如下：
void deleteNum(char *input, int k) {
int len, i;
len = strlen(input);
if(k > len) {
printf("error:K > strlen(input)\n");
return;
}
while(k > 0) {
for(i = 0; i < len-1; i++){
if(input[i] > input[i+1])
break;
}
for(; i < len; i++) {
input[i] = input[i+1];
}
k--;
len--;
}
}
但是上面的算法有个问题，当删除a[i]之后，右从数字的最左边开始扫描，时间复杂度为O(n * k)，这样效率会比较低，如果可以考虑再删除a[i]之后，继续从a[i]开始比较，这样性能会提升很多。再删除a[i]之后，此时已知前面的i-1个数都小于删除的数字a[i]，那么将删除数字a[i]之后的整数中此时的数字a[i](删除之前为a[i+1])与a[i-1]比较，若此时a[i] >a[i-1]，则继续向右移动，如果此时a[i] < a[i-1]，则应该向左移动，删除a[i-1]。这样就利用了已经比较过的信息对上面的算法进行优化，优化后的算法实现如下：
void deleteNumOptimized(char *input, int k) {
int len, i, j;
len = strlen(input);
if(k > len)
{
printf("error\n");
return;
}
i = 0;
while(k > 0) {
if(i == 0 || input[i] < input[i+1]){
while(i < len-1 && input[i] < input[i+1]) {
i++;
}
} else {
while(i >0 && input[i] < input[i-1]) {
i--;
}
}
for(j = i; j < len; j++) {
input[j] = input[j+1];
}
k--;
len--;
}
}
这题属于比较简单的题型，从这个题中可以看出多应用已经得到的信息，可以对算法进行优化。
在面试笔试过程中，写代码要先判断数字的长度是否小于k值，这个细节也比较重要。