leetcode 402. 移掉 K 位数字

题目链接：leetcode 402

1.题目

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

2.示例

1）示例 1 ：
输入：num = “1432219”, k = 3
输出：“1219”
解释：移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219 。

2）示例 2 ：
输入：num = “10200”, k = 1
输出：“200”
解释：移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

3）示例 3 ：
输入：num = “10”, k = 2
输出：“0”
解释：从原数字移除所有的数字，剩余为空就是 0 。

3. 问题分析

先用一个map记录0-9数字对应的从小到大的位置（可以使用栈来存储），同样选择一个数字，我们更希望这个数字的位置靠前，所以从后往前把数字位置压入栈，我们开始每一个位置去判断从0-9是否可以填入当前位置，那么需要满足以下条件：
1）该数字没有被用完
2）该数字位置大于前面使用的所有数字的位置
3）选了该数字后，保守还能凑齐num.size()-k个字符
依次对0-9进行判断并更改对应栈即可
需要注意要对前缀0的情况进行单独处理

4.代码

class Solution {
public: 
    map<int,stack<int>> map1;
    string removeKdigits(string num, int k) {
        for(int i=num.size()-1;i>=0;i--)
            map1[num[i]-'0'].push(i);
        string ans="";int last=-1;
        if(num.size()-k==0) return "0";
        int cnt=0;
        for(int i=1;i<=num.size()-k;i++){
            for(int j=0;j<=9;j++)
                if(map1.count(j)!=0)
                    if(map1[j].size()>0){
                        while(!map1[j].empty()){
                            if(map1[j].top()>last) break;map1[j].pop();
                        }
                        if(!map1[j].empty()&&cnt+num.size()-map1[j].top()>=num.size()-k){
                            last=map1[j].top();
                            char c=j+'0';
                            if(j!=0||ans!="")ans+=c;cnt++;
                            map1[j].pop();
                            break;
                        }
                    }
        }
        if(ans=="") return "0";
        return ans;
    }
};