LeetCode 402. Remove K Digits
已知一个使用字符串表示的非负整数num，将num中的k个数字移除， 求移除k个数字后，可以获得的最小的可能的新数字。(num不会以0开头,num长度小于10002)
输入 : num = “1432219” , k = 3
在去掉3个数字后得到的很多很多可能里，如1432、4322、2219、1219、 1229...;去掉数字4、3、2得到的1219最小!
class Solution{
public:
std::string removeKdigits(std::string num, int k){// 返回的结果用字符串来表示
}
};
分析
假设 num = 1432219 ; k = 1， 分别去掉1, 4, 3, 2, 2, 1, 9 得到数字:
分析与常识:
若去掉某一位数字，为了使得到的新数字最小，需要尽可能让得到的新数字优先 最高位最小，其次次高位最小， 再其次第3位最小...
算法设计
使用栈存储最终结果或删除工作，从高位向低位遍历num，
如果遍历的数字大于栈顶元素，则将该数字push入栈
如果小于栈顶元素则进行pop弹栈，直到栈为空或不能再删除数字
(k==0)或栈顶小于当前元素为止。
最终栈中从栈底到栈顶存储的数字，即为结果。
边界条件
1.当所有数字都扫描完成后，k仍然>0，应该做怎样的处理? 例如: num = 12345， k = 3 时。
2.当数字中有0出现时，应该有怎样的特殊处理? 例如: num = 100200, k = 1 时。
3.如何将最后结果存储为字符串并返回?
class Solution{
public:
std::string removeKdigits(std::string num, int k){
std::vector<int> S;//使用vector当作栈（因为vector可以遍历）
std::string result = "";存储最终结果的字符串
for(int i = 0;i <num.length();i++){//最高位循环扫描数字num
int number = num[i] - '0';//将字符型num转换整数；
while(S.size() != 0 && S[S.size() -1]>number && k>0){//当栈不空，栈顶元素大于number
S.pop_back();
k --;
}
if(number !=0 || S.size() != 0){
S.push_back(number);
}
while(S.size() && k>0){//如果栈不空仍然可以删除数字
S.pop_back();
k--;
for(int i = 0;i<S.size();i++){
result.append(1,'0'+S[i]);//转换成字符串
}
if(result == ""){
result = "0";
}
return result;
}
};
