556. Next Greater Element III

This problem is similar to 738. Monotone Increasing Digits. The key word of such problems is monotonicity, i.e., we need to judge the monotonicity of digits appearing in the given number.

In this problem, if the digit is monotone decreasing, then we cannot find the next greater number. Otherwise, we can solve it with the following steps:

1. At first, we use a list to represent the given number N where list.get(0) is the highest number.
2. Then, we backwardly traverse from list.size() - 1 to 1 to find the first i that list[i] > list[i - 1]. Record the i as pivot.
3. Next，we backwardly traverse from list.size() - 1 to i to find the first j that list[j] > list[i - 1].
4. At last, we swap list[i - 1] and list[j] and reverse list[i] to list[size - 1]

For example, if n = 1387543, the algorithm works as following:

• After step two, we get 13 87543
• After step three, we get 13 87543
• After swap, we get 14 87533
• After reverse, we get the final result 1433578

public int nextGreaterElement(int n) {
    List<Integer> numList = new ArrayList<Integer>();
    while( n != 0 ) {
        numList.add(0, n % 10);
        n /= 10;
    }
    int pivot = -1;
    for(int i = numList.size() - 1; i >= 0; i--) {
        if( i == 0 ) // The digit in n is monotone decreasing
            return -1;
        if( numList.get(i) > numList.get(i - 1) ) { // find the pivot
            pivot = i;
            for(int j = numList.size() - 1; j >= i; j--) {
                if( numList.get(j) > numList.get(i - 1) ) { // swap operation
                    int temp = numList.get(i - 1);
                    numList.set(i - 1, numList.get(j));
                    numList.set(j, temp);
                    break;
                }
            }
            break;
        }
    }
    long num = 0;
    for(int i = 0; i <= pivot - 1; i++)
        num = num * 10 + numList.get(i);
    for(int i = numList.size() - 1; i >= pivot; i--) // reverse from pivot to the end of list
        num = num * 10 + numList.get(i);
    return num > Integer.MAX_VALUE ? -1 : (int)num;
}