Leetcode題解 Python & C#：五月挑戰DAY13 Remove K Digits

給一個非負整數以 string 型態表示，移除 k 個數字，讓數字變成最小。

如果把它作DP，會超時，因為 num 的長度最多到10002。

不用 DP ，我們要來想想要如何從頭開始找起，並作篩選。

如果要讓結果是最小，那可想像會在一個範圍中，保留較小的，取走較大的。如此運作，直到挑出 k 個。

仔細觀察，被挑選過後的樣子。

"1432219", 3 -> "1219"

"4321234", 2 -> "21234"

"10200", 1 -> "200"

如果要排成最小，那麼會讓數列盡可能朝著「非升序排列」，也就是若左方大於右方，左方就會被挑走。

若左右相等或小於，則住右方移動。

"1432219"為例：

"0" # 預設

"01" # 左 < 右

"014" # 左 < 右

"014" "3" -> "01" "3" 挑走左方-> "013" (K = 2)

"013" "2" -> "01" "2" -> "012" (K = 1)

"0122" # 左 == 右

"0122" "1" -> "012" "1" (K = 0，將剩下的加入) -> "01219"

選完之後，先檢查 k 值，因為是 「非升序排列」，最後面的會是比較大的，若 k 有剩，從最後再拿走 k 個。

再去除前導零(leading zero)，用 lstrip("0")。

最後檢查答案是否為 "" ，是則回傳 "0" ，否則 result。

Python

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        result = "0"
        for i, c in enumerate(num):
            while c < result[-1] and k:
                result = result[:-1]
                k -= 1
            if k == 0:
                result += num[i:]
                break               
            result += c
                
        if k: result = result[:-k]
        result = result.lstrip("0")
        if result: return result
        return "0" 

C#

public class Solution {
    public string RemoveKdigits(string num, int k) {
        string result = "0";
        int n = result.Length;
        for(int i = 0; i < num.Length; i++)
        {            
            n = result.Length;
            while(num[i] < result[n - 1] && k > 0)
            {                
                result = result.Substring(0, n - 1);
                k -= 1;
                n -= 1;
            }
            if(k == 0)
            {
                n = num.Length;
                result = result + num.Substring(i, n - i);
                break;
            }
            result += num[i];            
        }
        n = result.Length;
        if(k > 0)
        {
            result = result.Substring(0, n - k);
        }
        result = result.TrimStart('0');
        if(result.Length == 0)
        {
            return "0";
        }            
        return result;            
    }
}