# 【LeetCode】 402. Remove K Digits

## Description
> 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.

> 給予一個非負數num用一個字串去表示，移除掉k個位元讓新的數字越小越好。

> 注意：
> * num的長度小於10002且會 ≥ k。
> * 給予的num不會有零在開頭。

## Example:

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.

## Solution

* 我們從高位元往低位元看，因為高位元的影響力比較高。
* 如果第`i`個位元大於`i + 1`個位元，那我們就移除掉`i`。
* 這樣就可以讓高位元的數字變小。
* 例如：`1432`，就移除`4`。
* 如果因為移除而導致最前面出現零，直接移除。
* 例如：`102`，移除`1`會變成`02`，無條件移除`0`(`k`不需要變)。
* 如果沒有任何位元`i`比`i + 1`大，那麼就移除最低位元(因為它數字最大)
* 例如：`12345`，就移除`5`。
* 如果`num`已經空了，補一個`0`然後直接回傳。

### Code

class Solution {
public:
    string removeKdigits(string num, int k) {
        while(k > 0 && !num.empty())
        {
            bool f = false;
            
            if(num[0] == '0')
            {
                num.erase(num.begin());
                continue;
            }
            
            for(int i = 0; i < num.length(); i++)
            {
                if(num[i] > num[i + 1])
                {
                    num.erase(num.begin() + i);
                    k--;
                    f = true;
                    break;
                }
            }
            
            if(!f)
            {
                num.pop_back();
                k--;
            }
        }
        while(num[0] == '0')
        {
            num.erase(num.begin());
        }
        if(num.empty())
            return "0";
        
        return num;
    }
};

###### tags: `LeetCode` `C++`