題目描述

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

• 空字符串被視為0。
• 如果結(jié)果中包含前導(dǎo)零，則需要將前導(dǎo)零刪除，最后刪除的前導(dǎo)零不用包含在移除的 k 個(gè)數(shù)字中。

輸入：

• 第一行輸入一個(gè)字符串，用來(lái)表示非負(fù)整數(shù) num。

• 第二行輸入一個(gè)整數(shù)，表示 k。

輸出:

• 輸出一個(gè)字符串，表示移除 k 位數(shù)字后所能得到的最小數(shù)字。

數(shù)據(jù)范圍：

• 0≤k≤ 字符串長(zhǎng)度 ≤100000，num 中不包含任何前導(dǎo) 0。

樣例

輸入樣例1

1432219
3

輸出樣例1

1219

樣例1解釋

• 移除掉三個(gè)數(shù)字 4,3,2 可形成一個(gè)新的最小的數(shù)字 1219。

輸入樣例2

10200
1

輸出樣例2

200

樣例2解釋

• 移掉首位的 1 剩下的數(shù)字為 200. 注意輸出不能有任何前導(dǎo)零。

輸入樣例3

10
2

輸出樣例3

0

樣例3解釋

• 從原數(shù)字移除所有的數(shù)字，剩余為空就是 0。

基本思想

1. 首先找出逆序?qū)?，在k內(nèi)刪除掉.
2. 如果k大于0，從后往前依次刪除，直至為0.
   3.判斷前導(dǎo)0的位置，同時(shí)考慮到如果此時(shí)處理后的字符串全部為0，那么就直接輸出一個(gè)0就可以。

C++ 代碼

#include <iostream>

using namespace std;

int main()
{
    string num;
    int k;
    cin >> num >> k;

    string res = "0";
    //刪除逆序?qū)?    for(int i = 0; i < num.size(); i++)
    {
        while(k && num[i] <res.back() )
        {
            res.pop_back();
            k--;
        }
        res += num[i];
    }
    //不存在逆序?qū)?，但是k不為0，從后往前一次刪除
    while(k--) res.pop_back();

    //如果有前導(dǎo)0，尋找前導(dǎo)0的位置
    int i = 0;
    while(i < res.size() && res[i] == '0') i++;

    //若整個(gè)數(shù)串都是0，則輸出0
    if(i == res.size() )puts("0");
    //前i - 1個(gè)都是前導(dǎo)零，所以從第i個(gè)輸出
    else cout << res.substr(i) << endl;
    return 0;   
}