leetcode-402 移掉K位數組

給定一個以字元串表示的非負整數 num，移除這個數中的 k 位數字，使得剩下的數字最小。

注意:

num 的長度小于 10002 且 ≥ k。

num 不會包含任何前導零。

示例 1 :

輸入: num = “1432219”, k = 3

輸出: “1219”

解釋: 移除掉三個數字 4, 3, 和 2形成一個新的最小的數字 1219。

針對該問題，顯然很好的解決辦法便是貪心

從高位開始周遊整數，即在移除的數字在k的範圍内，盡可能選擇移除較小的數值

string removeKdigits(string num, int k) {
    vector<int> S;
    string result = "";
    for (int i = 0;i < num.length(); ++i) {
        int number = num[i] - '0';
        while(S.size() != 0 && S[S.size() - 1] > number && k) {
            S.pop_back();
            k--;
        }

        if (number != 0 || S.size()) {//處理前導零的情況
            S.push_back(number);
        }
    }

    while(S.size() && k) {
        S.pop_back();
        k--;
    }

    for (int i = 0;i < S.size(); ++i) {
        result.append(1,'0' + S[i]);
    }

    if (result == "") {
        return "0";
    }
    return result;
}