problem description:
Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:
The length of num is less than 10002 and will be ≥ k.The given num does not contain any leading zero. 要使得删除k位后的数字之最小，首位数字应该是前k+1中最小的那个，设该位置的下一位为temp，k++，则删除后的第二位数字应该是temp位到k+1位中最小的那个，以此类推，直到k=length。该算法是贪婪算法，每次从temp到k+1之间选择最小的。算法复杂度为o(kn)。 代码如下： class Solution { public: string removeKdigits(string num, int k) { int len=num.length(); int temp,i,j; char t; string result(len-k,'0'); t=num[0]; temp=0; j=0; if(k==len) { string res(1,'0'); return res; } else { while(k<len) { t=num[temp]; temp++; for(i=temp;i<k+1;i++) { if(num[i]<t) { t=num[i]; temp=i+1; } } result[j]=t; j++; k++; } //cout<<result<<endl; i=0; while(result[i]=='0'&&(i+1)<result.length()) { result=result.erase(i,1); } cout<<result; return result; } } };