移掉 K 位数字( LeetCode 402 )
一、题目描述
给你一个以字符串表示的非负整数 num
和一个整数 k
,移除这个数中的 k
位数字,使得剩下的数字最小。请你以字符串形式返回这个最小的数字。
二、题目解析
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 移掉 K 位数字( LeetCode 402 ):https://leetcode-cn.com/problems/remove-k-digits/submissions/
class Solution {
public String removeKdigits(String num, int k) {
// 初始化栈,用来存储需要保留的数字
Stack<Character> stack = new Stack<Character>();
// 初始化字符串,用来保留最后的结果
StringBuilder result = new StringBuilder();
// 从左到右遍历字符串 num
for(int i = 0 ; i < num.length();i++){
// 获取此时遍历的字符
char digit = num.charAt(i);
// 如果此时
// 1、栈不为空
// 2、栈顶元素大于此时遍历的字符
// 3、还没有删除足够多的数字,即 k > 0
// 那么这个时候需要把栈顶元素弹出
while(!stack.isEmpty() && stack.peek() > digit && k > 0){
// 把栈顶元素弹出
stack.pop();
// 记录删除的个数减 1
k--;
}
// 如果发现此时遍历的字符为 0 并且栈为空
// 那么就不要把 0 放入到栈中,否则最终的结果会以 0 开头
if(digit == '0' && stack.isEmpty()){
continue;
}
// 把符合要求的字符放入到栈中
stack.push(digit);
}
// 遍历完所有的字符后,如果发现还没有删除足够多的元素,那么需要继续删除
// 什么数字会出现这种情况呢?
// 比如数字为 123456789 ,删除的数字 k 为 1
while(!stack.isEmpty() && k > 0){
// 不断的弹出栈顶元素
stack.pop();
// 直到 k 为 0 位置
k--;
}
// 操作完毕之后,如果发现栈为空,按上面逻辑我们会返回字符 "" ,
// 但根据题目的示例 3,num = "10", k = 2 时,从原数字移除所有的数字,剩余为空就是 0
// 需要返回 "0"
if (stack.isEmpty()) return "0";
// 如果栈中还有元素
while(!stack.isEmpty()){
// 那么从栈顶到栈底把字符添加到 result 上
result.append(stack.peek());
// 同时不断的弹出栈顶元素
stack.pop();
}
// 由于 stack 中的栈底是数字的最高位,栈顶是最低位
// 所以此时 result 保存的顺序是最低位到最高位
// 需要执行一次翻转操作
return result.reverse().toString();
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 移掉 K 位数字( LeetCode 402 ):https://leetcode-cn.com/problems/remove-k-digits/submissions/
class Solution {
public:
string removeKdigits(string num, int k) {
// 初始化栈,用来存储需要保留的数字
stack<char> s;
// 初始化字符串,用来保留最后的结果
string result = "" ;
// 从左到右遍历字符串 num
for(int i = 0 ; i < num.length();i++){
// 获取此时遍历的字符
int digit = num[i];
// 如果此时
// 1、栈不为空
// 2、栈顶元素大于此时遍历的字符
// 3、还没有删除足够多的数字,即 k > 0
// 那么这个时候需要把栈顶元素弹出
while(!s.empty() && s.top() > digit && k > 0){
// 把栈顶元素弹出
s.pop();
// 记录删除的个数减 1
k--;
}
// 如果发现此时遍历的字符为 0 并且栈为空
// 那么就不要把 0 放入到栈中,否则最终的结果会以 0 开头
if(digit == '0' && s.empty()){
continue;
}
// 把符合要求的字符放入到栈中
s.push(digit);
}
// 遍历完所有的字符后,如果发现还没有删除足够多的元素,那么需要继续删除
// 什么数字会出现这种情况呢?
// 比如数字为 123456789 ,删除的数字 k 为 1
while(!s.empty() && k > 0){
// 不断的弹出栈顶元素
s.pop();
// 直到 k 为 0 位置
k--;
}
// 操作完毕之后,如果发现栈为空,按上面逻辑我们会返回字符 "" ,
// 但根据题目的示例 3,num = "10", k = 2 时,从原数字移除所有的数字,剩余为空就是 0
// 需要返回 "0"
if (s.empty()) return "0";
// 如果栈中还有元素
while(!s.empty()){
// 那么从栈顶到栈底把字符添加到 result 上
result += s.top();
// 同时不断的弹出栈顶元素
s.pop();
}
// 由于 s 中的栈底是数字的最高位,栈顶是最低位
// 所以此时 result 保存的顺序是最低位到最高位
// 需要执行一次翻转操作
reverse(result.begin(), result.end());
return result;
}
};
3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 移掉 K 位数字( LeetCode 402 ):https://leetcode-cn.com/problems/remove-k-digits/submissions/
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
# 初始化栈,用来存储需要保留的数字
stack = []
# 从左到右遍历字符串 num
for digit in num:
# 如果此时
# 1、栈不为空
# 2、栈顶元素大于此时遍历的字符
# 3、还没有删除足够多的数字,即 k > 0
# 那么这个时候需要把栈顶元素弹出
while k and stack and stack[-1] > digit:
stack.pop()
k -= 1
# 把符合要求的字符放入到栈中
stack.append(digit)
return ''.join(stack[:len(stack) - k]).lstrip('0') or "0"