删除k位数字求最大数算法错误排查：输入1239438输出不符

问题背景 #

需求为：给定数字长度n、需删除位数k（满足0 < k < n ≤ 2000），删除k位后得到最大可能的数值。当前代码在输入n=7、k=3、num=1239438时输出9438，但用户认为正确结果应为9843，需排查错误原因。

错误原因拆解 #

1. 多余且错误的反转比较逻辑 #

代码末尾将栈生成的字符串反转后转成整数，再取两者最大值，这完全违背题目要求。删除k位数字得到的合法结果必须是原数字的子序列（保持原有字符顺序），反转后的字符串根本不是原数字的子序列，属于逻辑冗余且错误的操作。

2. 对题目要求的理解偏差 #

用户预期的结果9843并非原数字的子序列，说明用户可能误解了题目：

• 如果题目要求保持原数字顺序，则9438是正确结果，原代码的单调栈逻辑是对的，只是多了错误的反转比较步骤；
• 如果题目允许删除k位后重新排列剩余数字，则原代码的单调栈逻辑完全不适用，需要重新实现。

修正方案 #

方案1：保持原数字顺序求最大子序列 #

删除错误的反转比较逻辑，直接输出栈生成的合法子序列即可：

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        String num = sc.next();
        Stack<Character> stack = new Stack<>();
        
        // 参数合法性校验
        if (num.length() != n || n > 2000 || k <= 0 || k >= n) {
            System.out.println("Error!!!");
            return;
        }
        
        // 构建单调栈，保留最大子序列
        for (int i = 0; i < n; i++) {
            char c = num.charAt(i);
            // 当前数字大于栈顶时，弹出栈顶（删除较小的前位），直到k耗尽或栈顶更大
            while (!stack.isEmpty() && k > 0 && stack.peek() < c) {
                stack.pop();
                k--;
            }
            stack.push(c);
        }
        
        // 处理剩余未耗尽的k，删除末尾的k位
        while (k > 0) {
            stack.pop();
            k--;
        }
        
        // 拼接结果并输出
        StringBuilder sb = new StringBuilder();
        for (char c : stack) {
            sb.append(c);
        }
        System.out.println(sb.toString());
    }
}

输入验证：n=7、k=3、num=1239438，输出9438，这是符合“保持原顺序”要求的最大子序列。

方案2：允许重新排列剩余数字求最大值 #

若题目允许删除后重新排列，需统计数字出现次数，从9到0优先选取数字：

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        String num = sc.next();
        int remainCount = n - k;
        
        // 参数合法性校验
        if (num.length() != n || n > 2000 || k <= 0 || k >= n) {
            System.out.println("Error!!!");
            return;
        }
        
        // 统计每个数字的出现次数
        int[] digitCount = new int[10];
        for (char c : num.toCharArray()) {
            digitCount[c - '0']++;
        }
        
        StringBuilder sb = new StringBuilder();
        // 从9到0依次选取数字，凑够剩余位数
        for (int i = 9; i >= 0; i--) {
            while (digitCount[i] > 0 && remainCount > 0) {
                sb.append(i);
                digitCount[i]--;
                remainCount--;
            }
            if (remainCount == 0) break;
        }
        
        System.out.println(sb.toString());
    }
}

输入验证：n=7、k=3、num=1239438，输出9843，匹配用户预期的结果。

内容的提问来源于stack exchange，提问作者Hesam Yaghoubi