# [402. Remove K Digits](https://leetcode.com/problems/remove-k-digits/)
tags: `leetcode`

[TOC]

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

## **Ideas**
1. 因為刪除的數字一定是從最左位元開始
2. 且數字必須從最大的開始刪除
3. 因此創建一個stack，保存未刪除的數字
4. 當新的數字進來時與stack[-1]做判斷，如下

    while stack is not empty && stack[-1] > n && k > 0:
        stack.pop()
        k--

5. TC(n), SC(n)
## **code**
Python 3

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        if num == '0' or len(num) <= k:
            return '0'
        s = []
        
        for n in num:
            while s and k and s[-1] > n:
                s.pop()
                k -= 1
            s.append(n)
            
        if k:
            s = s[:-k]
            
        return ''.join(s).lstrip('0') or '0'

c++ version

class Solution {
public:
    string removeKdigits(string num, int k) {
        if ((num.size() <= k) || (num == "0"))
            return "0";
        string res;
        for (auto ch: num) {
            while (!res.empty() && k && res.back() > ch) {
                res.pop_back();
                --k;
            }
            if ((!res.empty()) || (ch != '0'))
                res.push_back(ch);
        }
        while (!res.empty() && k) {
            res.pop_back(), --k;
        }
        return res.size()? res: "0";
    }
};