求解删数问题 贪心法

删数问题可以使用贪心算法进行求解。贪心算法的思路是每次选择当前最优的解决方案，最终得到全局最优解。

具体来说，对于这个问题，我们可以从高位到低位扫描数字，如果当前数字比后面的一个数字大，那么就删除当前数字，这样可以保证删除的数字最小。如果删除的数字不足k个，那么我们可以从低位开始继续删除数字，直到删除了k个数字为止。

下面是一个具体的实现：

def delete_num(num, k):
    num_list = list(num)
    i = 0
    while k > 0 and i < len(num_list) - 1:
        if num_list[i] > num_list[i+1]:
            num_list.pop(i)
            k -= 1
            if i > 0:
                i -= 1
        else:
            i += 1
    # 如果还需要删除数字，从末尾开始删
    while k > 0:
        num_list.pop()
        k -= 1
    return "".join(num_list)

其中num是要删除数字的字符串，k是要删除的数字个数。该函数返回删除数字后的字符串。

时间复杂度为$O(n)$，其中n是数字的位数。

相关问题

求解删数问题：给定共有n位正整数d，去掉其中任意k<=n个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数d和正整数k。用贪心法编写程序找出剩下数字组成的新数最小的删数方案。

题目要求：给定共有n位正整数d，去掉其中任意<=k个数字后，剩下的数字按原次序排列组成一个新的正整数。对于给定的n位正整数d和正整数k，用贪心法编写程序找出剩下的数字组成的新数最小的删除数字方案。

解题思路：我们可以从高位到低位逐位考虑，如果当前位的数字比下一位大，那么这个数字就可以被删除。当我们删除k个数字后，我们就可以将剩下的数字以原次序组合成一个新数，保证其最小。