移除K个数字

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;
      
    }
};