描述
給定一個以字符串表示的非負整數 num，移除這個數中的 k 位數字，使得剩下的數字最小。

num的長度小于10002，且將≥k。給定的num不包含任何前導零。

您在真實的面試中是否遇到過這個題？
樣例
Example 1:

Input: num = “1432219”, k = 3
Output: “1219”

Example 2:

Input: num = “10200”, k = 1
Output: “200”
說明:去掉4、3、2三個數字，形成最小的新數字1219。
Example 3:

Input: num = “10”, k = 2
Output: “0”
num的長度小于k

思路：
官方思路：

給定一個數字序列如526 ，如果要求我們只刪除一個數字，那么從左到右，我們有5,2，6三個選擇，我們將每一個數字和它的左邊進行比較，從2開始，小于它的左邊5，我們應刪除5。
這個定義我們的貪心規則，每個數字都如此。直到滿足一些條件 結束：如 保存的數字為空，或者已經刪除啦k位數字。

注意一些特殊情況：
（1）單調遞增數據，貪心規則不好使，直接刪除數據最后k位，然后返回。
（2）k==0,返回原數據。
（3）在貪心規則里刪除的數字小于k位，如刪除了A位，我們需要在貪心外刪除原始數據最后的k-A 位。
代碼：

class Solution:def removeKdigits(self, num: str, k: int) -> str:numStack = []# 構造一個單調遞增的數字序列for digit in num:while k and numStack and numStack[-1] > digit:numStack.pop()k -= 1numStack.append(digit)# 遞增情況 將最后剩下的K位Trunk:返回整個列表#在while 循環里刪除數字小于k位 如m位，將while后面得到的數據 直接刪除最后k-m位，注意此時代碼里的k=k-m。因為已經在while k減去了m#在K ==0的情況下 返回原始數據numStackfinalStack = numStack[:-k] if k else numStack# 把前導零串起來return "".join(finalStack).lstrip('0') or "0" C=Solution() d=C.removeKdigits("1432219",k=3) print(d)

結果：1219

總結

以上是生活随笔為你收集整理的LeetCode移掉k位数字（贪心算法）python的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。