402. Remove K Digits

402. Remove K Digits

題意

給定一個字串 num 代表數字，移除 k 個字元，讓數字維持最小

限制

• 1 <= k <= num.length <= 105

• num consists of only digits.

• num does not have any leading zeros except for the zero itself.

思考

• 要讓數字最小，要盡量從左方移除較大的數字

  • 盡量組成遞減數列

  • monotonic stack

• 若開頭是0則直接移除，才不會組成不合法的數字

Solution

class Solution {
public:
    string removeKdigits(string num, int k) {
        const int n = num.size();
        string s = "";
        for (int i = 0; i < n; i += 1) {
            while (k > 0 && !s.empty() && s.back() > num[i]) {
                s.pop_back();
                k -= 1;
            }

            s.push_back(num[i]);

            if (s.size() == 1 && s.back() == '0') {
                s.pop_back();
            }
        }

        while (k > 0 && !s.empty()) {
            s.pop_back();
            k -= 1;
        }

        return s.empty() ? "0" : s;
    }
};