移掉 K 位数字

[编程题]移掉 K 位数字

热度指数：4124 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个以字符串表示的数字 num 和一个数字 k ，从 num 中移除 k 位数字，使得剩下的数字最小。如果可以删除全部数字，则结果为 0。

1.num仅有数字组成

2.num是合法的数字，不含前导0

3.删除之后的num，请去掉前导0（不算在移除次数中）

数据范围：num的长度满足 $1 \le k \le n \le 10^5 \$ ，保证 num 中仅包含 0~9 的十进制数

示例1

输入

"1432219",3

输出

"1219"

说明

移除 4 3 2 后剩下 1219

示例2

输入

"10",1

输出

"0"

示例3

输入

"100999",3

输出

"9"

算法知识视频讲解

Python2

比卡姆贝特

要最小化，尽可能的是删除左侧“大的”值。因为删除后会有后面的值递补上来，所以只要当前值可以删除（删除个数<K)而且当前值比后面的递补值大，那就可以删除这个值。

        st=collections.deque()
        cnt=0
        for i in range(len(num)):
            while cnt<k and len(st)>0 and st[-1]>num[i]:
                st.pop()
                cnt=cnt+1
            st.append(num[i])

发表于 2021-11-19 00:43:24 回复(1)