题目描述

任务要求去除输入数字字符串中连续出现的相邻递减数字。具体规则如下：

- 游戏结果返回字符串，必须去除k个相邻递减数字。 - 如果输入数字已经按顺序排列，要达到丢弃k个相邻递减数字的目标，应去掉末尾k个字符。


            
     思路分析
        
     
                  这是一个常见的问题，需要遍历数字字符串，判断相邻数字是否递减。如果发现递减情况，就将该相邻对记录下来，最后决定保留前几项，去掉后面的k个递减对。            
      
            优化思路：为了减少递归或多次遍历带来的时间复杂度，可以使用栈数据结构，逐字符扫描，维护一个递减计数器。当遇到递减的情况时，记录k的值，并进行必要的跳过处理。        
     
    
    
    
            
     时间复杂度分析
        
     
                  该方法的核心逻辑使用了一个栈来跟踪递减数字。每个数字最多被处理两次（入栈和出栈），由于内层循环的次数等于数字的长度N，因此时间复杂度为O(N)。            
      
            空间复杂度方面，栈存储了所有需要处理的N个数字，因此空间复杂度为O(N)。        
     
    
    
    
            
     代码实现
        
                 public class Solution {                public String removeKdigits(String num, int k) {                    if (num == null || num.isEmpty()) {                        return "";                    }                    if (k == 0) {                        return num;                    }                    if (k >= num.length()) {                        return "0";                    }                    // 以实际字符长度为目标                    int targetLength = num.length() - k;                    LinkedList
      
        stack = new LinkedList<>();                    for (int i = 0; i < num.length(); i++) {                        char c = num.charAt(i);                        // 如果发现前一位大于后一位，则弹出前一位                        // 并减少k的数量                        while (!stack.isEmpty() && stack.peekLast() > c && k > 0) {                            stack.removeLast();                            k--;                        }                        stack.addLast(c);                    }                    // 防止结果中有前导零，需要记录是否已经遇到了非零数字                    int leadingZeroCount = 0;                    StringBuilder result = new StringBuilder(targetLength);                    for (Character c : stack) {                        if (result.length() == targetLength) {                            break;                        }                        if (leadingZeroCount == targetLength) {                            result.append(c);                            leadingZeroCount--;                        } else if (c == '0' && leadingZeroCount < targetLength) {                            // 还是前导零，继续跳过                            continue;                        } else {                            if (c != '0') {                                leadingZeroCount++;                            }                            result.append(c);                        }                    }                    if (result.length() == 0) {                        return "0";                    }                    return result.toString();                }            }        
      
    
    
    
            
     测试示例结果