402. 移掉K位数字

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

在保持顺序的情况下，尽可能让较小的数充当较高位。

用一个栈来计较。
如果要进的数字比栈顶要大，并且可以删。直接将该数字丢弃。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    string removeKdigits(string num, int k) {
        //在保持顺序的情况下，尽可能让较小的数充当较高位。
        
        std::vector<int> S;
        std::string result = "";
        for(int i = 0; i < num.length(); i++){
            int number = num[i]-'0';
            //比当前栈顶元素大，并且能删除（k>0）,直接丢弃。
            while(S.size() != 0 && S[S.size()-1] > number && k > 0){
                S.pop_back();
                k--;
            }
            //0 不能在第一个位置。即不允许“0132”
            if(number != 0 || S.size()!= 0){
                S.push_back(number);
            }
        }
        
        // 处理“123456789”的情况。
        while(S.size() != 0 && k > 0){
            S.pop_back();
            k--;
        }
        for(int i = 0; i < S.size(); i++){
            result.append(1,'0'+S[i]);
        }
        if(result == "") return "0";
        return result;
    }
};