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].

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
重点是找到breakPoint, 多列几个test case就能明白怎么写了
7752 -> 6999
1541 -> 1499
85 -> 79
941 -> 899

分三步
1. 找到拐点
2. 拐点位置之前重新找拐点，新拐点位置之前所有值减1
3. 新拐点之后所有位置上的值为9

class Solution {
    public int monotoneIncreasingDigits(int N) {
        int[] arr = convertToArray(N);
        
        int i = getBreakPoint(arr);
        i = updateBeforeBreakPoint(arr, i);
        
        return getFinalNumber(arr, i);
    }
    
    private int getFinalNumber(int[] arr, int i) {
        int rt = 0;
        for (int j = 0; j < 9; j++) {
            if (j >= i + 1) {
                rt = 9 + rt * 10;
            }else if (arr[j] != 0) {
                rt = arr[j] + rt * 10;
            }
        }
        
        return rt;
    }
    
    private int updateBeforeBreakPoint(int[] arr, int i) {
        
        while (i > 0 && i < 9) {
            if (arr[i] >= arr[i - 1]) {
                break;   
            }
            arr[i - 1] = arr[i - 1] - 1;
            i--;
        }
        
        return i;
    }
    
    private int getBreakPoint(int[] arr) {
        
        int i = 1;
        while (i < 9) {
            if (arr[i] < arr[i - 1]) {
                break;
            }
            i++;
        }
        
        return i;
    }
    
    private int[] convertToArray(int N) {
        int[] arr = new int[9];
        
        for (int i = 8; i >= 0; i--) {
            arr[i] = N % 10;
            N /= 10;
        }
        
        return arr;
    }
}

流弊写法，从后往前
credit: barkfanleen3@gmail.com

class Solution {
    public int monotoneIncreasingDigits(int N) {
        int res = 0;
        int pre = Integer.MAX_VALUE;
        int offset =1;
        while(N != 0) {
            int digit = N % 10;
            if(digit > pre) {
                res = digit * offset - 1;
                pre = digit -1;
            }else {
                res = res + digit * offset;
                pre = digit;
            }
            offset *= 10;
            N = N/10;
        }
        return res;
    }
    
}