Java solution (similar to DFS)


  • 0

    The idea is to put each digit into a pool (array) digits[]. Then, starting finding the smallest number greater than n from the left-most digit.
    Beside, instead of using the length or number of digits, I use level to count the length of the number. As a result, the left-most digit can be obtained by n/level.
    There are two choices when picking a digit from the pool.
    (1) Pick the same digit as n_i, while n_i is the ith digit in n. Then, find the smallest number which greater than n%level.
    (2) Pick the smallest digit which greater than n_i . We can calculate the smallest number from the pool and then sum with n_i * level.

    public class Solution {
        long getMin(int[] digits){ // 
            long ret = 0;
            for (int i=0; i< 10; i++) {
                while (digits[i] > 0) {
                    ret *= 10;
                    ret += i;
                    digits[i]--;
                }
            }
            return ret;
        }
        long helper(long n, long level, int[] digits) {
            if (level==0 ) return -1;
            int firstDigit = (int) (n / level);
            digits[firstDigit]--;
            long ret = helper(n%level, level/10, digits);
            digits[firstDigit]++;
            if ( ret != -1 ) return firstDigit*level + ret;
            int nextHeightDigit = firstDigit;
            for (int i=firstDigit+1; i<10; i++) {
                if (digits[i] > 0) {
                    nextHeightDigit = i;
                    break;
                }
            }
            if (nextHeightDigit == firstDigit) return -1;
            digits[nextHeightDigit]--;
            return nextHeightDigit*level + getMin(digits);
        }
        public int nextGreaterElement(int n) {
            if (n<10) return -1;
            int[] digits = new int[10];
            long level = 1, temp = n;
            while (temp > 0) {
                int digit = (int) (temp % 10);
                digits[digit]++;
                temp /= 10;
                level *= 10;
            }
            long ret = helper((long)n, level/10, digits);
            return ret == -1 || ret > (long) Integer.MAX_VALUE ? -1: (int) ret;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.