输入一个最多 1000 位的正整数 𝑛 ，去掉其中任意 𝑠 个数字后剩下的数字按原左右次序组成一个新的整数。 编程对给定的 𝑛 和 𝑠 ，寻找一种方案使得剩下的数字组成的新数最小。 输入 第一行一个长度不超过 1000 位的正整数n. 第二行一个整数 𝑠 [ 1 , 500 ] s小于正整数n的长度。 输出 输出新的正整数。 样例输入 复制 175438 4 样例输出 复制 13 提示 需要去掉前导0 答案保证结果大于0

```python def remove_digits_to_minimize(n, s): stack = [] remove_count = s for digit in n: # 当栈非空、还能删除、且栈顶数字大于当前数字时，删除栈顶数字 while stack and remove_count > 0 and stack[-1] > digit: stack.pop() remove_count -= 1 stack.append(digit) # 如果还有剩余删除次数，从末尾删除 result = ''.join(stack[:len(stack) - remove_count]) # 去除前导零，但保证结果不为空 result = result.lstrip('0') return result if result else '0' if __name__ == "__main__": n = input().strip() s = int(input().strip()) print(remove_digits_to_minimize(n, s)) ``` 算法思路： 1. 贪心策略：从左到右遍历数字，维护一个单调递增栈 - 当栈顶数字大于当前数字且还能删除时，删除栈顶数字 - 这样可以保证高位数字尽可能小 2. 处理过程： - 遍历输入数字的每一位 - 使用栈保存最终结果 - 通过比较栈顶和当前数字决定是否删除 3. 特殊情况处理： - 遍历结束后如果还有删除次数，从末尾删除 - 去除结果中的前导零 - 保证结果不为空（至少为"0"） 示例说明： 输入：`175438`，`s=4` 1. 处理'1'：栈=[1] 2. 处理'7'：栈=[1,7] 3. 处理'5'：删除7，栈=[1,5] 4. 处理'4'：删除5，栈=[1,4] 5. 处理'3'：删除4，栈=[1,3] 6. 处理'8'：栈=[1,3,8] 7. 删除末尾1位：栈=[1,3] 输出：`13` 时间复杂度：O(n)，n为输入数字的长度 空间复杂度：O(n) [2026-01-11 12:43:19 | AI问答 | 476点数解答]