# 402. Remove K Digits

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

### Constraints:
`1 <= k <= num.length <= 105`
`num consists of only digits.`
`num does not have any leading zeros except for the zero itself.`

## 解題
好難，被擊敗了，參考 [youtube教學](https://www.youtube.com/watch?v=cFabMOnJaq0&ab_channel=NeetCode) 使用 monotonic stack 的技巧。因為在高位的數會主導整個數的大小，所以會希望數列盡量由小到大排列，所以我們希望維護一個 ascending monotonic stack，由於它會限制你只能刪掉 k 個元素，所以在 stack 中 pop 掉 k 個元素便停止。

### Python

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        if k >= len(num):
            return "0"
        
        stack = []
        for c in num:
            while k > 0 and stack and stack[-1] > c:
                stack.pop()
                k -= 1
            stack.append(c)
        
        stack = stack[:len(stack) - k]
        
        ret = ''.join(stack)
        return str(int(ret))

目前過不了，卡在測試項目中 int 與 str 之間的轉換超過他的最大值。

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack = []
        
        for digit in num:
            while stack and k > 0 and stack[-1] > digit:
                stack.pop()
                k -= 1
            stack.append(digit)
        
        # If k > 0, remove remaining k digits from the end of the stack
        # 有可能遍歷num後k還沒用完，也就是說後面的digits都比前面的大，沒有觸發置換
        stack = stack[:-k] if k > 0 else stack
        
        # Remove leading zeros
        result = ''.join(stack).lstrip('0')
        
        # Handle edge case where result might be empty
        return result if result else '0'