【面试经典】求删去K个数字后的最小值（贪心算法）

面试官：给出一个整数，从该整数中去掉K个数字，要求剩下的数字形成的新整数尽可能小

假设给出一个整数1593212，删除三个数字，新整数的最小情况是1212

30200，删去一个数字，新整数的最小情况是200

解题思路：

这个题目要求我们删除K个数字，我们不妨把问题简化一下，如果只删除一个数字，如何让新整数的值变得最小？

这时我们可能会想到优先删除这组数字中最大的数字，但是这是不对的，举例说明：3549中删除9后是354，删除5后是349，所以不能这样想。

数字的大小固然重要，但是数字的位置更加重要，一个整数的最高位哪怕减小1，对整个数字影响都很大。

所以我们把原来的数从左到右进行比较，如果发现某一个数字比他右边的数字大，那么删除该数字后，必然会使该数位的值减小，因为右边比他小的数顶替了他。

我们利用栈的特性，但不是利用栈，让所有数字依次入栈，当某个数字需要删除时，让该数字出栈，最后输出剩下的字符型结果

我们来看图：下面以整数541270936，k=3为例

当遍历到数字5，数字5入栈 原整数 541270936 stack 5        

 

当遍历到数字4时，发现4<5，所以数字5出栈，数字4入栈。

 

原整数 541270936 stack 4        

3.当遍历到数字1的时候，4>1,所以4出栈，1入栈

原整数 541270936 stack 1        

4.然后遍历2，7，依次入栈

stack 127      

5，遍历到0时，7>0,则栈顶的7出栈，0进行入栈

stack 120      

6.我们的删除次数已经用完，将剩下数字一起写入栈中

stack 120936   

代码展示

//删除整数的K个数字，获得删除后的最小值 #include<iostream> using namespace std; void RemoveDidits(string num,int k){ int length=num.length(); char stack[length]; int newlength=length-k; //遍历所有的数字 int top=0; for(int i=0;i<length;i++){ //当栈顶元素大于遍历到的数字时，栈顶元素出栈，新的元素入栈 while(top>0&&num[i]<stack[top-1]&&k>0){ top--;//栈顶元素出栈 k--; stack[top]=num[i];//新的元素入栈 } stack[top++]=num[i];//剩余元素入栈，这个最先进行一次，然后依次进行判断 } //找到栈中第一个非零数字的位置，依次构建新的整数字符串 int offset=0; while(offset<newlength&&stack[offset]=='0'){ offset++; } for(int i=offset;i<newlength;i++){ cout<<stack[i]; } cout<<endl; } int main(int argc, char const *argv[]) { RemoveDidits("541270936",3); RemoveDidits("1593212",3); RemoveDidits("30200",1); RemoveDidits("10",2); return 0; }

结果展示