402.Remove K Digits

Tags: Medium Greedy

Links: https://leetcode.com/problems/remove-k-digits/

---

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.

Note:

• The length of num is less than 10002 and will be ≥ k.
• The given num does not contain any leading zero.

Example 1:

Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2:

Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3:

Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

---

class Solution {
public:
    string removeKdigits(string num, int k) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        for (int i = 0; i < k; ++i) {
            int n = num.size(), pre = 0;
            bool hasFind = false;
            string tmp;

            for (int pos = pre + 1; pos < n; ++pos) {
                if (num[pos] - '0' < num[pre] - '0') {
                    hasFind = true;
                    tmp = num.substr(0, pre) + num.substr(pos);
                    break;
                }
                else pre = pos;
            }

            if (hasFind) num = tmp;
            else num = num.substr(0, n - 1);
        }

        int n = num.size(), pos = 0;
        while (pos < n - 1 && num[pos] == '0') ++pos;
        return n == 0 ? "0" : num.substr(pos);
    }
};

属于贪心问题的删数问题，相关联的有：

• 洛谷-P1106 删数问题（一本通-1321：【例6.3】删数问题(Noip1994)）
• 洛谷-P1323 删数问题