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])))