首页 > 试题广场 >

移掉 K 位数字

[编程题]移掉 K 位数字

热度指数：4474 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个以字符串表示的数字 num 和一个数字 k ，从 num 中移除 k 位数字，使得剩下的数字最小。如果可以删除全部数字，则结果为 0。

1.num仅有数字组成

2.num是合法的数字，不含前导0

3.删除之后的num，请去掉前导0（不算在移除次数中）

数据范围：num的长度满足 $1 \le k \le n \le 10^5 \$ ，保证 num 中仅包含 0~9 的十进制数

示例1

输入

"1432219",3

输出

"1219"

说明

移除 4 3 2 后剩下 1219

示例2

输入

"10",1

输出

"0"

示例3

输入

"100999",3

输出

"9"

算法知识视频讲解

Java

pein531

首要目的是删除高位的大数（数组中排在索引小的位置），才能使得数字尽可能小。那么我们可以维持一个从栈底到栈顶单调不减的单调栈，在从高位向低位遍历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)

唐氏综合征

贪心算法思想，每次移除剩下的都是最优解:

思路：要想每次都移除后使得剩余的最小，那么就必须找到可能的降序列，出现降序时，移除前面的较大值，并把当前的较小值加入队列，这样构成的数字才是当前的最小值，每一步都取最优解，当k个取完时则得到了全局最优解：

 public static String removeKnums(String num, int k) {
        if (k >= num.length()) return "0";
        LinkedList<Character> queue = new LinkedList<>();
        for (int i = 0; i < num.length(); i++) {
            while (!queue.isEmpty() && queue.peekFirst() == '0') queue.pollFirst();
            while (!queue.isEmpty() && k > 0 && num.charAt(i) <= queue.peekLast()) {
                queue.pollLast();
                k--;
            }
            queue.offer(num.charAt(i));
        }
        if (k != 0) return num.substring(0, num.length() - k);
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) sb.append(queue.pop());
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

发表于 2024-09-06 20:40:26 回复(0)

Java

菲尼克斯弗兰克

单调栈且注意去除前导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)

Java

17c89

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)

C++

M_yeah

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num string字符串
     * @param k int整型
     * @return string字符串
     */
    string removeKnums(string s, int k) {
        int n = s.length();
        int m = n - k; //选取m个数
        if(k>=n) return "0";
        vector<int> v(n, 0);
        vector<int> c(m, 0);
        for (int i = 0; i < n; i++) {
            v[i] = s[i] - '0';
        }

        int idx = -1;
        for (int i = 0; i < m; i++) {
            int min = INT_MAX;
            for (int j = idx + 1; j < n; j++) {
                int remain = m-i-1;
                if ((v[j] < min) && (n - j - 1 >= remain)) {
                    min = v[j];
                    idx = j;
                }
            }
            c[i] = min;
        }
        string res;
        idx = 0;
        while (idx<m && c[idx] == 0) idx++;
        if(idx==m) return "0";
        for (int i = idx; i < m; i++) {
            res.push_back(c[i] + '0');
        }
        return res;

    }
};

发表于 2024-07-23 11:41:58 回复(0)

刷刷刷114

#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)

JavaScript Node

矜持的微笑

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)

C++

AsherChi

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)

Java

汪旭阳

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)

Java

牛客930848623号

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)

牛客38477449号

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)

Python2

比卡姆贝特

要最小化，尽可能的是删除左侧“大的”值。因为删除后会有后面的值递补上来，所以只要当前值可以删除（删除个数<K)而且当前值比后面的递补值大，那就可以删除这个值。

        st=collections.deque()
        cnt=0
        for i in range(len(num)):
            while cnt<k and len(st)>0 and st[-1]>num[i]:
                st.pop()
                cnt=cnt+1
            st.append(num[i])

发表于 2021-11-19 00:43:24 回复(1)

提交观点

问题信息

贪心字符串栈单调栈

难度：

12条回答 61收藏 5503浏览

通过挑战的用户

查看代码

那就开摆

2022-09-18 23:19:48
正在卷的乌龟很刻苦

2022-09-14 16:42:56
Serena_Lin

2022-09-14 15:50:06
Asphyxiay

2022-09-14 02:12:27
小小快乐啊

2022-09-11 20:55:02

移掉 K 位数字

输入

输出

说明

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题