LeetCode_108_MonotoneIncreasingDigits

LeetCode

发布日期: 2022-06-15

更新日期: 2022-06-15

文章字数: 1k

阅读时长: 4 分

阅读次数:

1. question: 单调递增的数字（中等）

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

给定一个整数 n ，返回小于或等于 n 的最大数字，且数字呈单调递增。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/monotone-increasing-digits

示例 1:

1 2	输入: n = 10 输出: 9

示例 2:

1 2	输入: n = 1234 输出: 1234

示例 3:

1 2	输入: n = 332 输出: 299

提示:

1	0 <= n <= 109

2. answers

这道题本质上是求(0, n]之间最大的单调递增数。最开始想的是回溯法。利用当前位置上数字的取值区间，每次尽可能地选择最大值，来回溯选择。采用回溯法，需要注意的是，当前位置的取值区间，因为存在（当前位前面所有高位）借位的情况。

代码如下所示：

public class Solution_0108 {

    public boolean tag = false;

    public void recur(char[] chars, int index, int[] result, boolean isBorrow) {

        if(index == chars.length) {
            tag = true;
            return;
        }

        // 保存上一位的取值
        int pre;
        // 本位的取值范围最大值
        int range;

        if(index == 0) {

            // 判断是否是第一位
            pre = -1;
            range = chars[index] - '0';
        }
        else {

            pre = result[index - 1];

            // 注意，当前位的取值范围和上一位有关，如果上一位就是其最大值，那么本位的取值范围就是[0, 自身]
            // 如果上一位不是最大值，说明减了1，那么本位就是借位了，取值范围就是[0, 9]。
            // 注意，不一定是上一位，应该是所有高位中，只要有一位不是最大值，那么就发生了借位。
            if(!isBorrow) range = chars[index] - '0';
            else range = 9;
        }

        for (int i = range; i >= 0; i--) {

            // 满足 i>=pre
            if(i >= pre) {

                result[index] = i;

                // 递归
                // 注意，借位，如果前面已经发生了借位，那么也传入。
                recur(chars, index + 1, result, isBorrow || i != range);

                // 因为是从大到小进行选择的，所以只要找到了，那就是最优结果。
                if(tag) return;

                // 回溯，无需操作
            }
        }

    }

    public int monotoneIncreasingDigits(int n) {

        String number = n + "";
        char[] chars = number.toCharArray();

        int[] result = new int[chars.length];

        recur(chars, 0, result, false);

        int res = 0;

        for (int i = 0; i < result.length; i++) {
            res += result[i] * Math.pow(10, result.length - 1 - i);
        }

        return res;
    }

    public static void main(String[] args) {

        Solution_0108 s = new Solution_0108();

        int i = s.monotoneIncreasingDigits(999998);

        System.out.println(i);
    }
}

参考了题解，实际上没必要回溯。采用贪心法，只要找到不满足要求的最高位即可，将其减一，后续所有的值均为9。

但是怎么找呢？从左到右，如果从左到右，因为需要减一，就可能导致已经遍历的高位不满足要求（即低位影响高位）。比如99998，此时在最后98不满足要求，修改为89，显然99989也不满足要求。

因此需要从右到左遍历，因为本来就是从低位向高位遍历，即使修改了低位，导致高位不满足要求，但是在后续遍历的时候，就会修改高位的。代码如下所示：

public class Solution_0108_02 {

    public int monotoneIncreasingDigits(int n) {

        String s = n + "";

        char[] chars = s.toCharArray();
        int start = chars.length;

        // 从高位向低位遍历，找到不满足要求的最高位
        for (int i = chars.length - 1; i > 0; i--) {

            // 注意，因为数字最低是0，所以，既然小于前一个数，显然前一个数字不会为0
            if(chars[i] - '0' < chars[i - 1] - '0') {
                chars[i - 1] = (char) (chars[i - 1] - 1);
                start = i;
            }
        }

        // 找到最高位
        for (int i = start; i < chars.length; i++) {
            chars[i] = '9';
        }

        int res = 0;
        for (int i = 0; i < chars.length; i++) {
            res += (chars[i] - '0') * Math.pow(10, chars.length - 1 - i);
        }

        return res;
    }

    public static void main(String[] args) {

        Solution_0108_02 s = new Solution_0108_02();

//        int i = s.monotoneIncreasingDigits(999998);
//        int i = s.monotoneIncreasingDigits(10);
//        int i = s.monotoneIncreasingDigits(1234);
        int i = s.monotoneIncreasingDigits(332);

        System.out.println(i);
    }
}