移掉K位数字

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

注意:

num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。
示例 1 :

输入: num = "1432219", k = 3
输出: "1219"

解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例 2 :

输入: num = "10200", k = 1
输出: "200"

解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 :

输入: num = "10", k = 2
输出: "0"

解释: 从原数字移除所有的数字，剩余为空就是0。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-k-digits
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/*
从高位开始遍历，如果对应数字大于下一位，则去掉
暴力法太复杂，因此采用栈实现，对于num，一个一个push，那么若栈top大于push的数，则pop后再push，同时k--。（栈为空或k==0不能继续pop了）
还要考虑如下：
1，全部扫描后，k>0
2，遇到0
3，如何将最后结果存储为字符串返回
*/

// 使用vector充当栈，速度会快很多，空间也会少会很多
class Solution {
public:
    string removeKdigits(string num, int k) {
        if(k == num.size()) return "0";
        if(k == 0) return num;
        vector<char> _stack;
        // 遍历每一个输入的元素，目的是将按照顺序，将较小的数字放在高位，
        // 所以每次有较小的数字的时候，就去出栈，然后将较小的数字放到合适的位置上
        // 当然出栈的时候要关心k的数值，要保证k>0，出栈的数字就是我们所移除的数字
        for(int i = 0; i < num.size(); ++i) {
            while(!_stack.empty() && _stack.back() > num[i] && k > 0) {
                _stack.pop_back();
                --k;
            }
            // 不能在栈空的时候将0放入栈中
            if(num[i] != '0' || !_stack.empty()) {
                _stack.push_back(num[i]);
            }
        }
        while(k > 0) {
            _stack.pop_back();
            --k;
        }
        string re = "";
        for(int i = 0; i < _stack.size(); ++i)
            re += _stack[i];
        return re == "" ? "0" : re;
    }
};

// 使用栈（速度和空间都会变差）
// class Solution {
// public:
//     string removeKdigits(string num, int k) {
//         if(k == num.size()) return "0";
//         if(k == 0) return num;
//         stack<char> _stack;
//         for(int i = 0; i < num.size(); ++i) {
//             while(!_stack.empty() && _stack.top() > num[i] && k > 0) {
//                 _stack.pop();
//                 --k;
//             }
//             // 不能在栈空的时候将0放入栈中
//             if(num[i] != '0' || !_stack.empty()) {
//                 _stack.push(num[i]);
//             }
//         }
//         while(k > 0) {
//             _stack.pop();
//             --k;
//         }
//         string re = "";
//         while(!_stack.empty()) {
//             re = _stack.top() + re;
//             _stack.pop();
//         }
//         return re == "" ? "0" : re;
//     }
// };