###### tags: `Leetcode` `medium` `greedy` `stack` `python` `c++`

# 402. Remove K Digits

## [題目連結:] https://leetcode.com/problems/remove-k-digits/

## 題目:
Given string num representing a non-negative integer ```num```, and an integer ```k```, return the smallest possible integer after removing ```k``` digits from ```num```.

**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.

## 解題想法:
* 此題為給一字串，刪除k個字符使其數字最小
* 想法:
* 使用stack，希望其元素**順序從左到右的val為遞升，若不符合就刪掉**
* 若遍歷完，k還大於0，則刪除stack尾的元素
* 最終再將stack轉回string
* 注意須將左邊0去掉

## Python:

class Solution(object):
    def removeKdigits(self, num, k):
        """
        :type num: str
        :type k: int
        :rtype: str
        """
        #若刪除的數k==len(num) 
        if k==len(num):
            return '0'
        stack=[]
        #想法: 希望順序從左到右的val為遞升，若不符合就刪掉
        for val in num:
            #k>0: 代表還有數可以刪
            #stack非空
            #當前新的數比stack[-1]小
            while k>0 and stack and val<stack[-1]:
                stack.pop()
                k-=1
            stack.append(val)
        #k還>0: 刪除stack尾巴(因為由左到右 右邊為最大)
        for i in range(k):
            stack.pop()
        return ''.join(stack).lstrip('0') or '0'#把左邊0都去掉 
		#要or "0" 因為 ''.join(stack).lstrip('0')有可能結果為空字串
        
if __name__ == '__main__':
    result = Solution()
    ans = result.removeKdigits(num = "1432219", k = 3)
    print(ans)

## C++:
* vector轉string
* ex:
* vector < int > tmp
* string res ( tmp.**begin()**, tmp.**end()** )

class Solution {
public:
    string removeKdigits(string num, int k) {
        if (num.size()==k)
            return "0";
        vector<char> tmp;
        for (char val: num){
            while (!tmp.empty() && k>0 && val<tmp.back()){
                tmp.pop_back();
                k-=1;
            }
            tmp.push_back(val);
        }
        for (int i=0; i<k; i++){
            tmp.pop_back();
        }
        string res(tmp.begin(), tmp.end());
        //erase left 0
        while (!res.empty() && (res[0]=='0')){
            res.erase(res.begin());
        }
        return res.empty()? "0": res;

    }
};