LeetCode 402. Remove K Digits 2019-06-29

题目描述

给定一个以字符串表示的非负整数 num,移除这个数中的 k 位数字,使得剩下的数字最小。

注意:

num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。

tag

贪心 栈

样例

1
2
3
输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

算法1

(贪心) O(n)
思路

核心思想就是尽可能地使原数组保持递增。

要想是一个数尽可能小,最快的方法就是其高位尽可能小,,对这道题而言就是要把较小数字前面所有比它大的数删去来使之变成高位。

复杂度分析:
python 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
if len(num) <= k:
return '0'

stack = []

for digit in num:
while k > 0 and stack and int(stack[-1]) > int(digit):
stack.pop()
k -= 1
stack.append(digit)

while k > 0:
stack.pop()
k -= 1

return ''.join(stack).lstrip('0') or '0'