1、問題描述

給定一個(gè)以字符串表示的非負(fù)整數(shù) num挖帘，移除這個(gè)數(shù)中的 k 位數(shù)字完丽，使得剩下的數(shù)字最小。

注意:

• num 的長(zhǎng)度小于 10002 且 ≥ k拇舀。
• num 不會(huì)包含任何前導(dǎo)零逻族。

示例 1 :

輸入: num = "1432219", k = 3
輸出: "1219"
解釋: 移除掉三個(gè)數(shù)字 4, 3, 和 2 形成一個(gè)新的最小的數(shù)字 1219。
示例 2 :

輸入: num = "10200", k = 1
輸出: "200"
解釋: 移掉首位的 1 剩下的數(shù)字為 200. 注意輸出不能有任何前導(dǎo)零骄崩。
示例 3 :

輸入: num = "10", k = 2
輸出: "0"
解釋: 從原數(shù)字移除所有的數(shù)字聘鳞，剩余為空就是0薄辅。

2、思考與分析

3抠璃、貪心規(guī)律

4站楚、使用棧來優(yōu)化求解

5、需要注意的問題

• 當(dāng)所有數(shù)字都掃描完成后搏嗡，k仍然>0窿春，應(yīng)該做怎樣的處理? 例如: num = 12345， k = 3 時(shí)采盒。
• 當(dāng)數(shù)字中有0出現(xiàn)時(shí)旧乞，應(yīng)該有怎樣的特殊處理? 例如: num = 100200, k = 1 時(shí)。
• 如何將最后結(jié)果存儲(chǔ)為字符串并返回?

6磅氨、代碼實(shí)現(xiàn)

#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution
{
public:
    string removeKdigits(string num, int k)
    {
        vector<int> S;  // 使用vector當(dāng)作棧尺栖，方便遍歷操作
        string result = "";  // 存儲(chǔ)最終結(jié)果

        for (int i = 0; i < num.length(); i++)  // num.size() is ok!
        {
            int number = num[i] - '0';  // 數(shù)字字符轉(zhuǎn)整型數(shù)字 '3' -> 3

            // 這個(gè)循環(huán)的作用是：在k還有機(jī)會(huì)的情況下(k > 0)，
            // 要將S中烦租，從后到前延赌，比number大的全部刪除掉
            while (S.size() != 0 && S[S.size() - 1] > number && k > 0)
            {
                // S.size() != 0 說明還沒有將num的字符壓入到S中，或者被彈空了
                // S[S.size() - 1] > num 說明新來的數(shù)字小左权，比當(dāng)前S尾部的元素值更有利于使整體變小
                // k > 0 說明還有機(jī)會(huì)刪除數(shù)字
                S.pop_back();  // 當(dāng)上述三個(gè)條件都滿足時(shí)皮胡，彈出S尾部元素
                k --;  // 用掉一次彈出數(shù)字的機(jī)會(huì)
            }

            // 如果上述循環(huán)不滿足條件
            // 如果number != 0 ，那就可以將其壓入
            // 如果number == 0赏迟，但只要S.size() != 0就可以將其壓入
            // 這兩點(diǎn)保證是因?yàn)椋瑪?shù)字不能以一個(gè)0或者一串連續(xù)的0開頭
            // if (number != 0 || S.size() != 0)
            if (number != 0)
            {
                // 只所以能到這一步蠢棱，是因?yàn)楸仍搉umber大的锌杀，在k > 0范圍內(nèi)，全部被干掉了泻仙，
                // 當(dāng)前S.size()會(huì)終止一下
                // 不過當(dāng)前number是0的話糕再，雖然全部把前面的干掉了，但是0不能當(dāng)作首元素
                S.push_back(number);
            }
        }

        // 這種情況是玉转，k的次數(shù)沒有用完突想，就像12345678這種一樣
        // 注意：這里的S.size() != 0 是有必要的，因?yàn)樽詈罂赡苤皇Ａ宋膊康?
        // 而這些0是沒有壓入的S中究抓，所以這種情況就是猾担，S為空，但k > 0還滿足刺下，num也遍歷完了
        while (S.size() != 0 && k > 0)
        {
            // 只能從尾部用剩下的機(jī)會(huì)刪除
            S.pop_back();
            k --;
        }

        // 到目前位置绑嘹，S中剩下的元素，就是經(jīng)過元素刪除后滿足條件的
        for (int i = 0; i < S.size(); i ++)
        {
            result.append(1, '0' + S[i]);
        }

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

        return result;
    }
};

int main()
{
    string num = "10200";

    int k = 1;
    Solution S;
    string res = S.removeKdigits(num, k);

    cout << res << endl;
    return 0;
}