移除 K 位数字的最小值

【编程题目 |200分】移除 K 位数字的最小值【2021 H1,H2, 2022, 2023  2023 Q2考试题 B卷 OD考试题】

时间限制：C/C++ 1秒，其他语言 2秒

空间限制：C/C++262144K，其他语言524288K

64bit IO Format：%lld

本题可使用本地IDE编码，不能使用本地已有代码，无跳出限制，

编码后请点击”保存并调试”按钮进行代码提交。

■ 题目描述

【移除 K 位数字的最小值】

输入描述

第一行输入一个非负整数字符串，第二行输入一个整数n

输出描述

输出从该字符串中取出n个字符后剩下的字符组成的最小的数（不改变字符顺序）

输入

2615371

4

输出

131

给出一个数字组成的字符串，去除指定个数的字符，剩余的组成最小值。

这个解题思路可以是递归，按照顺序取剩余个数的字符，组成数字，依次比较获取，但是可能超时。

例如 6525441，去除 4 个字符，得到 241。

最优解是删除出现的第一个左边>右边的数，

例如第一次删除 6，因为 6>5，变成 525441；

第二次删除 5，5>2，变成 25441，第三次是 5，第四次是 4，结果为 241。

代码实现

Golang

package main

import (
    "fmt"
)

剩余50%内容，购买单篇文章或订阅会员后查看

CPP

#include<bits/stdc++.h>

using namespace std;

// 移掉k位数字使得到的最小
string RemoveKdigitsMinValue(string num, int k)
{
    vector<char> stk;
    for (auto &digit: num) {
        while (!stk.empty() && stk.back() > digit && k--) {
            stk.pop_back();
        }

剩余50%内容，购买单篇文章或订阅会员后查看

JAVA

import java.util.*;

public class RemoveKNum {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String s = sc.nextLine();
        int m = sc.nextInt();

剩余50%内容，购买单篇文章或订阅会员后查看

Python

剩余50%内容，购买单篇文章或订阅会员后查看

STICK永久会员

打赏 收藏 海报 链接