给定一个以字符串表示的数字 num 和一个数字 k ，从 num 中移除 k 位数字，使得剩下的数字最小。如果可以删除全部数字，则结果为 0。
1.num仅有数字组成
2.num是合法的数字，不含前导0
3.删除之后的num，请去掉前导0（不算在移除次数中）
数据范围：num的长度满足 
，保证 num 中仅包含 0~9 的十进制数
[编程题]移掉 K 位数字
首要目的是删除高位的大数（数组中排在索引小的位置），才能使得数字尽可能小。那么我们可以维持一个从栈底到栈顶单调不减的单调栈，在从高位向低位遍历num的各位数字时，不断检查栈中元素的单调性。
- 一旦这个单调性被破坏，就表示高位数大，低位数小，这时候如果还剩下删除操作，就将栈顶元素弹出再把当前元素压栈（相当于移掉一个数）；
- 满足单调不减就直接把当前数字压栈。
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num string字符串
* @param k int整型
* @return string字符串
*/
public String removeKnums (String num, int k) {
// write code here
Stack<Integer> stack = new Stack<>();
for(int i = 0; i < num.length(); i++){
int digit = num.charAt(i) - '0';
while(!stack.isEmpty() && stack.peek() > digit && k > 0){
stack.pop();
k--;
}
stack.push(digit);
}
while(k > 0 && !stack.isEmpty()){
stack.pop();
k--;
}
// 去掉前导0
StringBuilder res = new StringBuilder();
Stack<Integer> resStack = new Stack<>();
while(!stack.isEmpty()){
resStack.push(stack.pop());
}
while(!resStack.isEmpty() && resStack.peek() == 0){
resStack.pop();
}
while(!resStack.isEmpty()){
res.append(resStack.pop());
}
// 所有字符都移除干净了就返回0
return res.length() > 0? res.toString(): "0";
}
}
编辑于 2022-03-30 15:48:04
回复(0)
单调栈且注意去除前导0！
import java.util.*;
public class Solution {
public String removeKnums (String num, int k) {
if (k >= num.length()) return "0";
ArrayDeque<Character> stack = new ArrayDeque<>();
for (char c : num.toCharArray()) {
while (k > 0 && !stack.isEmpty() && c < stack.peek()) {
stack.pop();
k--;
}
stack.push(c);
}
StringBuilder res = new StringBuilder();
while (!stack.isEmpty()) {
res.insert(0, stack.pop());
}
// 去除前导0！！！
int i = 0;
while (i < res.length()) {
if (res.charAt(i) == '0') i++;
else break;
}
if (i > 0 && res.length() > 1) return res.delete(0, i).toString();
else return res.toString();
}
}
发表于 2022-01-26 14:35:38
回复(0)
#include <string>
#include <vector>
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num string字符串
* @param k int整型
* @return string字符串
*/
string removeKnums(string num, int k) {
if (k == 0) return num;
vector<char> v;
v.reserve(num.size());
int s = 0;
for (auto ch : num) {
while (!v.empty() && s < k && ch < v.back())
{
v.pop_back();
s++;
}
v.emplace_back(ch);
}
if (s < k) {
v.erase(v.begin() + (v.size() - k + s), v.end());
}
int index = 0;
for (; index < v.size(); index++)
{
if (v[index] != '0') break;
}
v.erase(v.begin(), v.begin() + index);
v.emplace_back(0);
return v[0] == 0 ? "0" : v.data();
}
};
编辑于 2024-04-22 09:05:42
回复(0)
function removeKnums( num , k ) {
// write code here
const stack=[]
for(let i of num){
while(k>0&&stack.length&&stack[stack.length-1]>i){
stack.pop()
k--
}
if(i!=='0'||stack.length!==0){
stack.push(i)
}
}
while(k>0){
stack.pop()
k--
}
return stack.length===0?'0':stack.join('')
}
发表于 2023-06-28 21:28:30
回复(0)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num string字符串
* @param k int整型
* @return string字符串
*/
string removeKnums(string num, int k) {
// write code here
stack<int> stk;
int cur = 0;
int cur_k = 0;
while(cur < num.length()){
while(!stk.empty() && (num[cur]-'0') < stk.top() && cur_k < k){
stk.pop();
cur_k++;
}
stk.push(num[cur] - '0');
cur++;
}
while(cur_k < k){
stk.pop();
cur_k++;
}
string res = "";
while(!stk.empty()){
res.push_back(stk.top()+'0');
stk.pop();
}
// 去除前导0
cur = res.length()-1;
while(res[cur] == '0'){
res.pop_back();
cur--;
}
reverse(res.begin(), res.end());
return res == ""? "0":res;
}
};
发表于 2022-09-08 15:42:43
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num string字符串
* @param k int整型
* @return string字符串
*/
public String removeKnums (String num, int k) {
if (k > num.length()) return "0";
// write code here
if (k == 0) {
if (num.length() == 0){
return "0";
}else{
String m =num;
while(m.charAt(0)=='0'){
m=m.replaceFirst("0","");
}
return m;
}
}
char[] chs = num.toCharArray();
int tartgetPosition = 0;
int i= 1;
for (; i < chs.length; i++) {
int a = chs[i - 1] - '0';
int b = chs[i] - '0';
if (a>b){
tartgetPosition=i-1;
break;
}
}
if (i==chs.length){
tartgetPosition= chs.length-1;
}
char c = chs[tartgetPosition];
String s2 = num.replaceFirst("" + c, "");
k--;
return removeKnums(s2, k);
}
}
发表于 2022-02-20 10:34:29
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num string字符串
* @param k int整型
* @return string字符串
*/
public String removeKnums (String num, int k) {
// write code here
Stack<Integer> stack = new Stack();
for(int i = 0;i < num.length();i++){
int digit = num.charAt(i)-'0';
while(k > 0 && !stack.isEmpty() && digit < stack.peek()){
stack.pop();
k--;
}
stack.push(digit);
}
while(k > 0 && !stack.isEmpty()){
stack.pop();
k--;
}
StringBuffer res = new StringBuffer();
while (!stack.isEmpty()){
res.append(stack.pop());
}
//trim leading zero
while (res.length() > 0 && res.charAt(res.length()-1) == '0'){
res.deleteCharAt(res.length()-1);
}
return res.length() == 0 ? "0" : res.reverse().toString();
}
}
/*
思路：利用单调栈特性，遍历字符串的每一位，如果当前数字大于前面的
的数字，就将该数出栈，需要出栈的个数减一，反之进栈；
若遍历完一次，k的值还大于0，证明出栈次数还不够，进行出栈操作，k次数减一；
新建一个stringbuffer往里面添加元素；
当字符串的最后一位是0，则删除最后一位0，然后返回结果
结果如果得出移除后的长度为0则为0，不为0则将数字进行反转后输出
*/
发表于 2021-12-27 16:44:49
回复(0)
class Solution: def removeKnums(self , num: str, k: int) -> str: # write code here if len(num) == k: return 0 stack = [] for i in range(len(num)): while stack and ord(num[i]) < ord(stack[-1]) and k: k -= 1 stack.pop() stack.append(num[i]) res = "" for i in range(len(stack)): if stack[i] != "0": res = "".join(stack[i:]) break return int(res) if len(res) != 0 else 0
发表于 2021-12-24 11:53:28
回复(0)
问题信息
难度：
9条回答
50收藏
3126浏览
通过挑战的用户
查看代码-
2022-09-18 23:19:48
-
2022-09-14 16:42:56 -
2022-09-14 15:50:06 -
2022-09-14 02:12:27 -
2022-09-11 20:55:02
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
