算法（蓝桥杯）贪心算法5——删数问题的解题思路

问题描述

给定一个高精度的正整数 n（n≤1000 位），需要删除其中任意 s 个数字，使得剩下的数字按原左右顺序组成一个新的正整数，并且这个新的正整数最小。例如，对于数字 153748，删除 2 个数字后，最小的数是 1348。

---

解题思路

1. 贪心算法

要解决这个问题，我们可以使用贪心算法。贪心算法在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的。

2. 维护单调递增栈

我们可以通过维护一个单调递增的栈来实现这个目标。具体步骤如下：

2.1 初始化栈

创建一个空栈 stack，用于存储最终结果中的数字。

2.2 遍历每个数字

遍历输入的高精度正整数 n 的每一位数字 num。

2.3 维护单调递增栈

• 弹出条件：当栈不为空（stack），且还需要删除数字（s > 0），且栈顶元素大于当前数字（stack[-1] > num）时，弹出栈顶元素，并减少 s 的值。这样做的目的是尽可能地让结果数的高位更小，从而使得整个数更小。

• 入栈操作：将当前数字 num 入栈。这一步是为了保留当前数字，以便后续继续判断。

2.4 处理剩余的删除操作

遍历结束后，如果 s 还大于0，说明原数是单调递增的。在这种情况下，直接去掉末尾的 s 个数字即可。因为从末尾去掉数字对结果数的影响最小。

2.5 拼接结果并处理前导0

• 拼接结果：将栈中的数字拼接成一个字符串。

• 处理前导0：使用 lstrip('0') 去掉前导0。如果去掉前导0后字符串为空（即原数删除后只剩下0），则返回 '0'。

3. 示例解释

以 n = "153748" 和 s = 2 为例，详细说明每一步的操作：

1. 初始化栈：stack = []。

2. 遍历每一位数字：

   • num = '1'：栈为空，直接入栈。stack = ['1']。

   • num = '5'：栈顶元素 '1' 小于 '5'，直接入栈。stack = ['1', '5']。

   • num = '3'：栈顶元素 '5' 大于 '3'，弹出 '5'，s 减1。stack = ['1']。然后 '3' 入栈。stack = ['1', '3']。

   • num = '7'：栈顶元素 '3' 小于 '7'，直接入栈。stack = ['1', '3', '7']。

   • num = '4'：栈顶元素 '7' 大于 '4'，弹出 '7'，s 减1。stack = ['1', '3']。然后 '4' 入栈。stack = ['1', '3', '4']。

   • num = '8'：栈顶元素 '4' 小于 '8'，直接入栈。stack = ['1', '3', '4', '8']。

3. 遍历结束后，s 为0，不需要再处理。

4. 拼接结果并处理前导0：''.join(stack).lstrip('0')，结果为 '1348'。

最终结果为 '1348'，这是删除2个数字后得到的最小数。

4. 代码实现

def min_number_after_delete(n, s):"""删除s个数字后得到的最小数:param n: 原始高精度正整数，字符串形式:param s: 需要删除的数字个数:return: 删除s个数字后得到的最小数，字符串形式"""stack = []# 遍历每个数字for num in n:# 当栈不为空且s大于0且栈顶元素大于当前数字时，弹出栈顶元素while stack and s > 0 and stack[-1] > num:stack.pop()s -= 1# 当前数字入栈stack.append(num)# 如果s还大于0，说明原数是单调递增的，直接去掉末尾的s个数字即可if s > 0:stack = stack[:-s]# 将栈中的数字拼接成字符串，并去掉前导0return ''.join(stack).lstrip('0') or '0'# 示例
n = "153748"
s = 2
print(min_number_after_delete(n, s))  # 输出：1348n = "1087"
s = 1
print(min_number_after_delete(n, s))  # 输出：87

5. 总结

通过维护一个单调递增的栈，我们可以有效地找到删除 s 个数字后得到的最小数。这种方法的时间复杂度为 O(n)，其中 n 是输入数字的长度，因为每个数字最多只会被入栈和出栈一次。希望这个解释能帮助你更好地理解这个问题的解法。如果有任何疑问，欢迎继续提问。