Java intuitive solution


  • 0
    C
    public static int monotoneIncreasingDigits(int N) {
    	if (isMonotone(N) == true) // Check if N is already a monotone number.
    		return N;
    	else
    		return nextLesserMonotone(N);
    	}
    
    public static int nextLesserMonotone(Integer num) {
    	char[] number = num.toString().toCharArray();
    		
    	// Handle 1-digit numbers.
    	if (number.length == 1) {
    		int digit = Character.getNumericValue(number[0]);
    		if (digit >= 1)
    			return digit - 1;
    		else
    			return 0;
    	}
    		
    	/*
    	 * * Algorithm is to make the smallest changes to the number (minimize
    	 * decrements to find the max). Once a digit has been decremented once,
    	 * if number now is not the max monotone number, then move on to the next digit,
    	 * because the max monotone number will not be a version of the number with
    	 * the current digit more decremented. Set this current digit to 9 before
    	 * moving onto the next (left) digit, because that will always produce the max,
    	 * because the final max monotone number will be guaranteed to have 9s in digit
    	 * positions that were changed (maximize the monotone number). 
    	 */
    	int index;
    	for (index = number.length - 2; index >= 0; index--) {
    			
    		// Cast to ASCII values, not integers.
    		if ((int) number[index + 1] > (int) number[index]) {
    			number[index + 1] = (char) (((int) number[index + 1]) - 1);
    			
    			// Check if number is a monotone each time number changes.
    			if (isMonotone(Integer.parseInt(new String(number))))
    				return Integer.parseInt(new String(number));
    		}
    			
    		number[index + 1] = '9';
    			
    	} // Loop decrements index one too many times.
    		
    	// If exited loop, then the digit at index 0 of number must be decremented.
    	number[index + 1] = (char) (((int) number[index + 1]) - 1);
    		
    	return Integer.parseInt(new String(number));
    }
    	
    public static boolean isMonotone(Integer num) {
    	char[] number = num.toString().toCharArray();
    
    	for (int index = number.length - 2; index >= 0; index--) {
    		if ((int) number[index + 1] < (int) number[index])
    			return false;
    	}
    
    	return true;
    }
    

Log in to reply
 

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