单调递增的数字

发表于
本文字数： 2k 阅读时长 ≈ 2 分钟

LeetCode每日一题，738. Monotone Increasing Digits

先看题目描述

rK3Zy6.png

大意就是给定一个整数 N，让我们返回小于等于 N 的最大的递增整数

算法和思路

首先判断该整数是否是递增整数，若是递增整数，则直接返回该整数即可；若不是递增整数，则找出最长递增序列，以整数 3344442 为例，我们找出的最长递增序列是 334444，由于最后的几个数字是重复出现的，我们应当取到最后的重复数字中的第一位，即取到其中的 334，最后返回的结果就是 334 × 10000 - 1 即 3339999

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int monotoneIncreasingDigits(int N) {
        if (N < 10) {
            return N;
        }
        int num = N;
        int len = -1;
        while (num != 0) {
            num /= 10;
            len++;
        }
        int i = 0;
        int cur = 0;
        int pre = 0;
        int res = 0;
        int temp = (int)Math.pow(10, len);
        int[] nums = new int[len + 1];
        for (; i <= len; i++) {
            cur = N / temp;
            if (pre <= cur) {
                nums[i] = cur;
                res = res * 10 + cur;
                N %= temp;
                temp /= 10;
                pre = cur;
            } else {
                break;
            }
        }
        if (i > len) {
            return res;
        } else {
            i--;
            while (i > 0 && nums[i - 1] == nums[i]) {
                i--;
                res /= 10;
            }
            return res * (int)Math.pow(10, len - i) - 1;
        }
    }
}

下面这个是看题解时在评论里看到的一个解法，思路就是从后往前遍历 N 的各位数字，若前一位的数字大于当前位的数字，则将前一位数字 - 1，并将当前位及之后的数字全部置为 9，遍历完后返回结果即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int monotoneIncreasingDigits(int N) {
        char[] nums = String.valueOf(N).toCharArray();
        int len = nums.length;
        for (int i = len -1; i > 0; i--) {
            if (nums[i] < nums[i - 1]) {
                nums[i - 1]--;
                for (int j = i ; j < len; j++) {
                    nums[j] = '9';
                }
            }
        }
        return Integer.parseInt(String.valueOf(nums));
    }
}

注意：将 char 数组转为整数需要用 Integer.parseInt(String.valueOf(nums)) 方法，我一开始用的 Integer.valueOf(nums.toString()) 方法就出问题了