给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:num 的长度小于 10002 且 ≥ k。num 不会包含任何前导零。
示例 1 :
输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例 2 :
输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 :
输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。
思路1：从头开始遍历字符组，如果当前数字大于栈顶则将其放入栈中，否则使用贪心算法移除栈顶元素。若未遍历完字符串k就已经减小为0，可以提前挑出循环以节省时间；若遍历完字符串k仍不为0，因为此时栈中数字是升序排列，所以可以依次去除栈顶的元素，更新k直至其为0，此时栈中剩余元素就是最终结果（当然还需要去除开头的‘0’）
def removeKdigits(self, num: str, k: int) -> str:
#考虑一般情况：
if len(num) == k:
return '0'
if k == 0:
return num
#定义栈和返回结果：
stack = []
res = ''
'''贪心算法：将字符串中的数字依次入栈，若当前字符大于栈顶数字，
弹出栈顶并更新k值直至k为0。若循环结束还k还不为0，则去掉栈顶
剩余的k个元素。'''
#定义遍历结束点：
end_point = -1
#遍历字符串：
for index, value in enumerate(num):
if len(stack) == 0 or int(value) >= int(stack[-1]):
stack.append(value)
else:
while len(stack) > 0 and int(value) < int(stack[-1]):
stack.pop()
k -= 1
if k == 0:
break
stack.append(value)
#当k为0时可以提前结束循环
if k == 0:
end_point = index
break
#讨论k的不同情况：
if k == 0:
res = ''.join(stack) + num[end_point+1:]
else:
while k != 0:
stack.pop()
k -= 1
res = ''.join(stack)
#去掉开头的‘0’：
if res == '':
return '0'
else:
index = 0
while res[index] == '0':
if index == len(res)-1:
return '0'
index += 1
return res[index:]
思路2：
1.从高位开始逐一查找每一位数字尽可能小的取值。其中，第 x 位数字的有效取值范围是 x-1 ~ k+x-1
2.找到最小值后记录最小值 min_num 以及对应的下标 min_index
3.设置下一轮的查找开始位置为 min_index + 1
4.循环此过程，直到完成所有数字的查找
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
num_length = len(num)
if num_length <= k:
return "0"
left_count = num_length - k
res = ""
count = 0
begin = 0
while count < left_count:
min_index = 0
min_num = float('inf')
for i in range(begin, k + count + 1):
# 找到最小数
if int(num[i]) < min_num:
min_index = i
min_num = int(num[i])
# 把找到的最小数加入结果列表
res += str(min_num)
# 设置下一轮查找范围的起点
begin = min_index + 1
count += 1
return "0" if len(res) == 0 else str(int(res))