Leetcode-738-单调递增的数字

题目描述

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）

示例 1:

输入: N = 10
输出: 9

示例 2:

输入: N = 1234
输出: 1234

示例 3:

输入: N = 332
输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。

算法思路

• 从左往右遍历各位数字，找到第一个开始下降的数字[i]，将[i]减1，然后将[i+1 …]各位数字全部置为9即可

  • 例如：1232123，从左往右遍历，找到第一个开始下降的数字3，将3改为2，然后将后面所有数字全部置为9，最后为：1229999 即为答案

• 【需要注意一点】：如果第一个开始下降的数字[i]，前面还有与其相等的数字，需要找到最前面的一个数字作为上面所说的[i]

  • 例如：13332，从左往右遍历，找到第一个开始下降的数字3
  • 往前再看下，是否还有等于3的数字，找到最前面那个3，将3改为2
  • 然后将后面的各个数字置为9，最后为：12999

class Solution {
    public int monotoneIncreasingDigits(int N) {
        // 1. 特判
        if(N < 10){
            return N;
        }

        // 数字转换成字符数组好进行处理
        char[] chars = String.valueOf(N).toCharArray();

        //  2. 从左到右遍历各位数字,找到第一个开始下降的数字idx
        int idx = 0;
        while(idx + 1 < chars.length && chars[idx] <= chars[idx + 1]){
            idx++;
        }

        // 3. 从头到尾都满足条件chars[i] <= chars[idx + 1]
        if(idx == chars.length - 1){            
            return N;                           // 整个数字符合要求，直接返回
        }

        // 3. 否则的话，说明出现了chars[idx] > chars[idx + 1] 的情况
        while(idx - 1 >= 0 && chars[idx - 1] == chars[idx]){  // 是否还有等于当前[i]的数字，找到最前面那个
            idx--;
        }
        chars[idx] = (char)(chars[idx] - 1);                    // 将第一个[i]--;
        // 接下来将所有[idx+ 1 ... ]全部置为9
        idx++;
        while(idx < chars.length){
            chars[idx] = '9';
            idx++;
        }

        // 4. 返回结果int
        return Integer.parseInt(String.valueOf(chars));
    }
}

复杂度分析

• 时间复杂度：O(logN)，其中 O(logN) 表示数字 N 的位数。我们遍历 O(logN) 的时间即能构造出满足条件的数字。

• 空间复杂度：O(logN)。我们需要 O(logN) 的空间存放数字 N 每一位的数字大小。

打赏