402.移掉K位数字
https://leetcode-cn.com/problems/remove-k-digits/
难度:中等
题目:
给定一个以字符串表示的非负整数num,移除这个数中的 k 位数字,使得剩下的数字最小。
注意:
num 的长度小于 10002 且≥ k。
num 不会包含任何前导零。
示例:
示例 1 :
输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例 2 :
输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 :
输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字,剩余为空就是0。
分析
这道题考察我们对于单调栈的理解。
当然前提我们需要了解,既然从左往后删除,当前数如果比栈顶的数字小时,我们应该持续出栈,
直到当前数字比栈顶的数字大,再将数字入栈。
另外,当字符串的所有数字保持升序,我们一个数字都没出栈,
但由于k没有使用完,此时应该返回num[:len(num) - k]的结果。
解题:
class Solution:
def removeKdigits(self, num, k):
ret = []
counts = len(num) - k
for i in num:
while ret and int(ret[-1]) > int(i) and k:
k -= 1
ret.pop()
ret.append(i)
return ''.join(ret[:counts]).lstrip('0') or "0"
欢迎关注我的公众号: 清风Python,带你每日学习Python算法刷题的同时,了解更多python小知识。
我的个人博客:https://qingfengpython.cn
网友评论