# 資訊

:::info
- Question: 402. Remove $K$ Digits
- From: Leetcode Daily Challenge 2024.04.11
- Difficulty: Medium
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

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:
:::success
* 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:
:::success
* Input: `num = "10200"`, `k = 1`
* Output: `"0"`
* Explanation: Remove all the digits from the number and it is left with nothing which is `0`.
:::

> Constraints:
:::success
* 1 <= `k` <= `num.length` <= $10^5$
* `num` consists of only digits
* `num` does not have any leading zeros except for the zero itself.
:::

---

# 解法

## 概念

> Ref: https://leetcode.com/problems/remove-k-digits/solutions/5006103/stack-monotonic-stack-python-simple-solution

看到 monotonnic stack 就怕了。。

其實這題主要在想到 greedy function，當然主軸跟 monotonic stack 比較接近。

先從簡單的情況看起，如果今天測資 `k=2`，而 `num` 是 ordering，假設是 increasing 的 `12345`，那我會希望 pop 掉 `45`，也就是最後面，如果 `num` 是 decreasing 的 `54321`，那我會希望 pop 掉 `54` 變成 `321`，差別在於從頭還是從尾巴 pop，但不論何種情況，都是單純的從特定一邊 pop，如果是解這種情況，就比較輕鬆

接著要 relax 一下假設，如果今天有 peak 在中間呢？也就是非 ordering，那我會 pop 掉對我來說不符合規則的情況，這邊情況就是我希望它是遞增或遞減，當然因為遞增會針對新進的元素處理，所以我使用遞增的方法。舉個例子，假設測資變成 `13524`，來實際走一次看看

1. 第一個 `1`，還是遞增的
2. 接著 `13`，還是遞增的
3. 接著 `135`，還是遞增的
4. 接著 `1352`，變成遞減了，這時候就要把壞蛋 `5` 抓出來，變成 `132`，然後再檢查一下，還是遞減，所以把壞蛋 `3` 也抓出來，變成 `12`，很好，現在是遞增
5. 繼續接上剩餘元素變成 `124`，沒有違背情況，很棒！

這樣就可以拿到解答！最後就是要注意幾個情況，一個是如果剛剛 pop 不夠多，`k` 還沒用完，那就按照最一開始單純的作法，遞增 array pop 掉最後面的就可以了。而如果有 leading 0 的話那也要記得移除。最後就是比較答案，如果空字串救回傳 0，不然就回傳該字串。

## 程式碼

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        # Create an empty stack
        stack = []

        # Pop first k element that is "NON-DECREASING" from head
        for i in range(len(num)):
            # Use while since we may pop out many items in such round
            while stack and stack[-1] > num[i] and k > 0:
                stack.pop()
                k -= 1
            # For each round, num[i] should be append into stack
            stack.append(num[i])
        # If the digits are now ordering, pop out first few element to meet criteria (Consider testcase like '54321')
        while k > 0:
            stack.pop()
            k -= 1
        # Remove leading 0
        while len(stack) > 0 and stack[0] == '0':
            stack.pop(0)
        # Return if stack is not empty, else return 0
        return ''.join( stack ) if stack else '0'

---

# 複雜度

## 時間複雜度

走訪過一次字串，那個 for loop 占了 $O(n)$


## 空間複雜度

空間部分有一個 `stack` 在那邊，也是 $O(n)$