LeetCode 738. Monotone Increasing Digits

738. Monotone Increasing Digits

Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits.

        (Recall that an integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.)

Example 1:
Input: N = 10
Output: 9
Example 2:
Input: N = 1234
Output: 1234
Example 3:
Input: N = 332
Output: 299
Note: N is an integer in the range [0, 10^9].           

复制

题目大意：给出一个数，返回比这个数小的最大的各个位上是单调递增的数

解法一：

这是我开始选择的方法，非常直白，但是直白简单的方法往往不是最佳的解法，提交到LeetCode上，给我抛出一个超时，可见效率有多低。首先写一个函数，判断一个数是否是符合要求的，如果不符合要求，就将这个数递减，直到找到符合的数为止，试想假如这个数是95555555555，那么符合题意的数是9，想想看要做多少次减法啊！！！！

public int monotoneIncreasingDigits(int N) {
        int n = N;
        while (!isIncreaseNum(n)){
            n--;
        }
        return n;
    }

    public boolean isIncreaseNum(int num){
        String str = Integer.toString(num);
        char[] chars = str.toCharArray();
        for (int i = 1 ; i < chars.length;i++){
            if (chars[i] < chars[i-1]) return false;
        }
        return true;
    }           

复制

解法二：

针对数字研究后，知道可以很容易的写出另外一种更优秀的解法。

public int monotoneIncreasingDigits(int N) {
        char[] chars = Integer.toString(N).toCharArray();
        int index = 0;
        for (int i = 1 ; i < chars.length ; i++){
            if (chars[i] == chars[index]) continue;
            if (chars[i] < chars[index]){
                chars[index] = (char)(chars[index] - 1);
                for (int j = index+1;j<chars.length;j++){
                    chars[j] = '9';
                }
                break;
            }else
            index = i;
        }
       return Integer.parseInt(new String(chars));
    }           

复制

本解法，采用 一个index值记录一个将要减一的一位，后面的所有位置为9即可。是不是非常简单呢？思路就不讲解了，也是非常的直白。

注意：

将一个char[]的数组转化为String类型，不可以直接调用toString()方法，查看char的toSting()方法，可以知道：

public String toString() {
    return getClass().getName() + "@" + Integer.toHexString(hashCode());
}           

复制

像这样返回的不是String类型；应该采用newString(chars)，转为String类型。

最后，string转为int：

Integer.parseInt() 也可以采用 Integer.valueOf()代替。           

复制