喜马拉雅算法笔试0924
100%, 0%
第二题快结束的时候想出来的思路，可惜结尾的 stack[:n - k] 写成 stack[:k] 了。。。
T2
题目
第一行输入两个整数 num 和 k，要求从 num 中删去 k 个数字，使得剩下的数字组成的数最小，并输出最小的整数。数据范围：k <= num.length <= 10^5
- 示例
- 输入：
10200 1 - 输出：
200
- 输入：
分析
本题考查贪心算法，每次优化可优化的最高位数字即可。可以证明，如果有某个可优化的高位没有优化，那么优化高位的方案一定是更优的。所以我们每次应当删除 num[i] > num[i + 1] 的最小的 i，适合用单调栈来做。时间复杂度：O(n)
代码
num, k = input().split()
k = int(k)
n = len(num)
if k == n:
print(0)
else:
stack = []
n_remove = 0 # 已经删去的数字个数
idx = 0
while n_remove < k and idx < n: # 删完 k 个或遍历完所有下标时跳出
# 去掉左侧更大的数字 然后加入 num[idx]
while stack and int(stack[-1]) > int(num[idx]):
stack.pop()
n_remove += 1
if n_remove == k:
break
stack.append(num[idx])
idx += 1
# 加入所有的剩余数字
stack.append(num[idx:])
print(int("".join(stack[:n - k])))
类似资料：