给定一个以字符串表示的数字 num 和一个数字 k ，从 num 中移除 k 位数字，使得剩下的数字最小。如果可以删除全部数字，则结果为 0。
1.num仅有数字组成
2.num是合法的数字，不含前导0
3.删除之后的num，请去掉前导0（不算在移除次数中）
数据范围：num的长度满足 
，保证 num 中仅包含 0~9 的十进制数
[编程题]移掉 K 位数字
import java.util.*;
// 栈：若s[i]比栈顶小, 持续弹出栈顶 788(6) → (6)
public class Solution {
public String removeKnums (String num, int k) {
char[] s = num.toCharArray();
int n = s.length, top = -1;
char[] stack = new char[n + 1];
stack[++top] = '0'; // 默认0：防止最终结果""空串
for (int i = 0; i < n; i++) {
while (k > 0 && top >= 0 && stack[top] > s[i]) {
top--;
k--;
}
stack[++top] = s[i];
}
while (k-- > 0) top--; // 剩余k
int i = 0; while (i < top && stack[i] == '0') i++; // 前导0
return String.valueOf(stack, i, top - i + 1);
}
}
发表于 2025-10-17 17:46:41
回复(0)
import java.util.*;
/**
* NC219 移掉 K 位数字
* @author d3y1
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param num string字符串
* @param k int整型
* @return string字符串
*/
public String removeKnums (String num, int k) {
// return solution1(num, k);
// return solution2(num, k);
return solution3(num, k);
}
/**
* 单调栈+贪心
* @param num
* @param k
* @return
*/
private String solution1(String num, int k){
if(k >= num.length()){
return "0";
}
Stack<Character> stack = new Stack<>();
for(char digit: num.toCharArray()){
// 单调栈(单调增)
while(!stack.isEmpty() && digit<stack.peek() && k>0){
// 贪心
stack.pop();
k--;
}
stack.push(digit);
}
// 继续移除
while(k-- > 0){
if(!stack.isEmpty()){
stack.pop();
}
}
// 保存结果
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty()){
sb.insert(0, stack.pop());
}
// 去掉前导0
String result = sb.toString();
if(result.startsWith("0")){
int index;
for(index=0; index<result.length(); index++){
if(result.charAt(index) != '0'){
break;
}
}
if(index < result.length()){
result = result.substring(index);
}else{
result = "0";
}
}
return result;
}
/**
* 单调栈+贪心
* @param num
* @param k
* @return
*/
private String solution2(String num, int k){
int n = num.length();
if(k >= n){
return "0";
}
Deque<Character> stack = new ArrayDeque<>();
for(char ch: num.toCharArray()){
// 单调栈(单调增)
while(!stack.isEmpty() && stack.peekLast()>ch && k>0){
// 贪心
stack.pollLast();
k--;
}
stack.offerLast(ch);
}
// 继续移除
while(!stack.isEmpty() && k>0){
stack.pollLast();
k--;
}
// 去掉前导0
while(!stack.isEmpty() && stack.peekFirst()=='0'){
stack.pollFirst();
}
// 保存结果
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty()){
sb.append(stack.pollFirst());
}
return sb.length()==0?"0":sb.toString();
}
/**
* 单调栈+贪心
* @param num
* @param k
* @return
*/
private String solution3(String num, int k){
int n = num.length();
if(k >= n){
return "0";
}
Deque<Character> stack = new ArrayDeque<>();
for(char ch: num.toCharArray()){
// 单调栈(单调增)
while(!stack.isEmpty() && stack.peekLast()>ch && k>0){
// 贪心
stack.pollLast();
k--;
}
stack.offerLast(ch);
}
// 继续移除
while(!stack.isEmpty() && k>0){
stack.pollLast();
k--;
}
// 保存结果
StringBuilder sb = new StringBuilder();
while(!stack.isEmpty()){
sb.append(stack.pollFirst());
}
// 去掉前导0
String result = sb.toString().replaceFirst("^0+", "");
return "".equals(result)?"0":result;
}
}
发表于 2025-02-03 11:34:24
回复(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)
单调栈且注意去除前导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)
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)
首要目的是删除高位的大数（数组中排在索引小的位置），才能使得数字尽可能小。那么我们可以维持一个从栈底到栈顶单调不减的单调栈，在从高位向低位遍历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)
问题信息
难度：
7条回答
61收藏
6442浏览
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
