给定一个正整数,去掉其中的k位数,剩下的数字按原先次序排列,如何让生成的数最小。
时间: 2024-05-11 15:18:34 浏览: 88
删数问题给定n 位正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个
4星 · 用户满意度95%
这是一个经典的贪心算法问题。我们可以从高位向低位遍历,每次选择删除当前位数后剩余数字中最小的数字。
具体实现可以使用一个栈来存储当前已经遍历过但是未确定位置的数字,同时维护一个计数器表示还需要删除多少个数字。每次遍历到一个新的数时,将其与栈顶元素比较,如果栈顶元素比当前数大,将栈顶元素弹出并将计数器减1,直到栈顶元素不再比当前数大或者计数器为0为止,然后将当前数入栈。
遍历结束后,如果还需要删除数字,则从栈顶弹出元素,直到删除足够的数字为止。最后将栈中的数字按原顺序拼接起来即可得到最小的数。
以下是 Python 代码实现:
```python
def remove_k_digits(num: str, k: int) -> str:
stack = []
for digit in num:
while stack and k > 0 and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
while k > 0:
stack.pop()
k -= 1
return ''.join(stack).lstrip('0') or '0'
```
其中,`lstrip('0')` 用于去掉结果中的前导零。
阅读全文