leetcode402. 移掉 K 位数字

题目：402. 移掉 K 位数字

参考：ye-shang-6

依据数字位数越高影响越大，从最高位挑选数字。例：num = 1432219, k=3，删去k=3个数字，那么就是保留length-k=7-3=4个数字。首先需要挑选首位数字，保证尽量小并且在num中的位置尽量靠左。可以将num = 1432219分为 1432 和 219两部分（保留最后3个作为保底，在之前的4位中找最小）此时start = 0, end = k。在[start,end]中选取一个最小的进行保留，返回最小数字的下标min_pos。找第二位的时候start = min_pos + 1. end +=1 如此类推直到选完 n-k 次。

对于前缀0，选择不把选取过程中的首个0加入结果字符串ans 但是 算作一次挑选step进行处理。

class Solution {
public:
    string removeKdigits(string num, int k) {
        if(num == "0" || num.length() == k) return "0";

        int step = num.length() - k; // 等价于从num中选取(num-k)个数字
        int minpos = -1; // 上一位被挑选值的位置
        string ans = "";
        while(step)
        {
            // 挑选这一步的数字
            int start = minpos + 1;
            int end = num.length() - step;
            char minval = num[start];
            minpos = start;
            for(int i=start+1; i<=end; i++)
            {
                if(num[i] < minval) 
                {
                    minval = num[i];
                    minpos = i;
                }
            }

            step--;
            if(minval == '0' && ans == "") continue;
            ans.push_back(minval);
        }

        return (ans == "")? "0" : ans;
    }
};