给定一个正整数,去掉其中的k位数,剩下的数字按原先次序排列,如何让生成的数最小。
时间: 2023-05-24 21:06:15 浏览: 334
删数问题给定n 位正整数a,去掉其中任意k≤n 个数字后,剩下的数字按原次序排列组成一个
4星 · 用户满意度95%
这是一个经典的贪心算法问题,可以使用单调栈求解。
具体做法如下:
1. 从左往右遍历原数的每一位,将其加入栈中,同时比较栈顶元素和当前元素的大小,如果栈顶元素大于当前元素且还没有删够k个数字,则弹出栈顶元素,重复该步骤。
2. 如果已经删够了k个数字或者遍历完原数的所有数字,则剩下的数字就是最终的结果。如果此时栈为空,则结果为0。
3. 去除结果前导0,输出。
代码实现如下:
```python
def remove_k_digits(num: str, k: int) -> str:
stack = []
# 遍历每一位数字
for n in num:
# 如果栈不为空且还可以删数且当前数字小于栈顶元素,弹出栈顶元素
while stack and k > 0 and n < stack[-1]:
stack.pop()
k -= 1
# 将当前数字加入栈中
stack.append(n)
# 如果还需要删数,则从栈顶依次删除数字
while k > 0:
stack.pop()
k -= 1
# 去除前导0,得到最终结果
res = "".join(stack).lstrip("0")
return res if res else "0"
```
时间复杂度为O(n),其中n为原数的位数。
阅读全文