算法-单调递增的数字

超、凢脫俗 2022-12-28 06:27 154阅读 0赞

# 算法-单调递增的数字 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/split-array-into-consecutive-subsequences/

## 1.2 题目描述 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]

# 2 从最往右 #

## 2.1 思路 ##

从左往右比：

*  如果发现当前数比前一个数小，则不符合题意，此时将前一位的数字减1，当前位及以后的所有位数字变为9，然后传入新的数字递归调用该解法求解
 *  如果当前数大于等于前一个数，则符合题意，继续探寻下一个数

## 2.2 代码 ##

## 2.3 时间复杂度 ##

![O(N)][O_N]

## 2.4 空间复杂度 ##

O(N)

# 3 贪心 #

class Solution { 
        public int monotoneIncreasingDigits(int N) { 
            // 从左往右考虑
            int remain = N;
            String ns = String.valueOf(N);
            int[] is = new int[ns.length()];
            int i = 0;
            while(remain != 0){ 
                is[i++] = remain % 10; 
                remain = remain / 10;
            }
            StringBuilder result = new StringBuilder(String.valueOf(is[is.length - 1]));
            for(int j = is.length - 2; j >=0; j--){ 
                if(is[j] >= is[j + 1]){ 
                    result.append(is[j]);
                } else{ 
                    // 将前一位减1
                    is[j + 1]--;
                    StringBuilder quickResult = new StringBuilder();
                    
                    int target = is.length - 1;
                    for(int k = j + 1; k < is.length - 1; k++){ 
                        if(is[k] < is[k+1]){ 
                            // 数减一后小于前一个数字了
                            // 此时需要把前一个数也减1
                            // 后面数就全为9
                            is[k+1]--;
                            continue;
                        }
                        target = k;
                        break;
                    }
    
                    // 从高位到低位添加经过调整已经满足的
                    for(int k = is.length - 1; k >= target; k--){ 
                        quickResult.append(is[k]);
                    }
                    
                    // 从当前target位开始的后面全部变为9
                    for(int k = target - 1; k >= 0; k--){ 
                        quickResult.append("9");
                    }
                    
                    return Integer.parseInt(quickResult.toString());
                }
            }
            return Integer.parseInt(result.toString());
        }
    }

# 参考文档 #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]: /images/20221120/1925d3c78a7b4fc48676315a7f9cde47.png
[O_N]: https://img-blog.csdnimg.cn/20201215103846657.png