738. Monotone Increasing Digits

This problem can be solved in greedy strategy:

1. At first, we use a list to represent the given number N where list.get(0) is the highest number.
2. Then, we traverse from 0 to list.size() - 1 to find the first i that list[i] > list[i + 1]
3. If we don't find such i, then return the given number. Otherwise, we backwardly traverse from i to 0 to find the first j that list[j] > list[j - 1] or until j equals 0.
4. list[j] minus one, and for all k > j, set list[k] to 9.

public int monotoneIncreasingDigits(int N) {
    // Represent N with a list
	List<Integer> num = new ArrayList<Integer>();
    while( N != 0 ) {
        num.add(0, N % 10);
        N /= 10;
    }
	
    for(int i = 0; i < num.size() - 1; i++) {
        if( num.get(i) > num.get(i + 1) ) { // find the first i that num[i] > num[i + 1]
            for(int j = i; j >= 0; j--) {
                if( j == 0 || num.get(j) > num.get(j - 1) ) { // find the first j that num[j] > num[j - 1]
                    num.set(j, num.get(j) - 1);
                    for(int k = j + 1; k < num.size(); k++) // set all num[k] where k > j to 9
                        num.set(k, 9);
                    break;
                }
            }
            break;
        }
    }
    int result = 0;
    for(int i = 0; i < num.size(); i++)
        result = result * 10 + num.get(i);
    return result;
}