难度: Medium
原题连接
内容描述
Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:
The length of num is less than 10002 and will be ≥ k.
The given num does not contain any leading zero.
Example 1:
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:
Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:
Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.
思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******
我们知道如果数字相等话，这个数字越靠左它代表的实际数值就越大，所以我们应该优先删除它
Just a few of my intuition to make myself more comfortable about why using greedy.
In fact, any time you see "smallest","as... as possible",
you should try greedy first and that might be a really nice solution.
By meaning greedy, we mean to start from most significant digit (left most digit).
If you can replace that digit (k>0) with a smaller number (by removing that digit), you remove it.
The following digit takes the place and the number becomes smaller.
And as you are operating from most significant digit, the resulting number is guaranteed to be the smallest.
class Solution(object):
def removeKdigits(self, num, k):
"""
:type num: str
:type k: int
:rtype: str
"""
if k == 0:
return num
stack = []
for c in num:
while k and stack and c < stack[-1]:
stack.pop()
k -= 1
stack.append(c)
while k:
stack.pop()
k -= 1
res = ''.join(stack).lstrip('0')
return res if res else '0'写的更精简就是：
class Solution(object):
def removeKdigits(self, num, k):
"""
:type num: str
:type k: int
:rtype: str
"""
if k == 0:
return num
stack = []
for c in num:
while k and stack and c < stack[-1]:
stack.pop()
k -= 1
stack.append(c)
res = ''.join(stack[:len(stack)-k]).lstrip('0')
return res if res else '0'