Nearest number with non-decreasing digits

Given a number N given in the form of array, with each index storing one digit of the number. Write code to change the number to the greatest number less than N, such that digits of that number are in non-decreasing order.
For example:

INPUT ARRAY: {1, 4, 3} (representing number 143)
OUTPUT : 139
INPUT ARRAY: {2, 2, 2, 1} (representing number 2221)
OUTPUT : 1999

Solution-1: Brute Force
The brute force approach is keep reducing the number (given in the form of array) unless the digits fall in the required order. For example, if number is 143, then we keep decrementing it by 1 and check if the digits are sorted in ascending order

ARRAY       NUMBER     ARE DIGITS SORTED
{1, 4, 2}     142        NO
{1, 4, 1}     141        NO
{1, 4, 0}     140        NO
{1, 3, 9}     139        YES

The answer is when the digits in array are in non-decreasing order. This solution will take lot of time (Checking the number at each step is also an added overhead.
Solution-2:
The logic is as below:

1. From the left side, find the first position of mismatch (where arr[i] > arr[i+1]).
2. Decrease the digit at index i and set all the digits from (i+1) till the end equal to '9'.
3. After point 2. the number after index i (including i) is in right order.
   But by decreasing arr[i], we might have created a mismatch between digit i and (i-1).
   Consider 2221, step-2 will make it 2219, and there is a mismatch at position (i-1) and i.
   Move back from i down to 0 and correct the mismatch if found.

Code:

import java.util.Scanner;
public class RitambharaTech
{
   public static void printNearestNonDecreasing(char[] str)
   {
      // Single Digit number
      if(str.length==1)
      {
         System.out.println(str);
         return;
      }
      int i=0;
      // Setting all digits after first mismatch to 9.
      for(; i<str.length-1; i++)
      {
         if(str[i] > str[i+1])
         {
            for(int j=i+1; j<str.length; j++)
               str[j] = '9';
            break;
         }
      }
      // Check mismatch at (i-1) and i
      if(i==str.length-1)
         System.out.println(str);
      else
      {
         str[i]--;
         for(int j=i; j>0; j--)
         {
            if(str[j-1]>str[j])
            {
               str[j] = '9';
               str[j-1]--;
            }
         }
         // Ignoring leading zeros while printing
         for(i=0; i<str.length; i++)
            if(str[i] != '0')
               break;
         for(; i<str.length; i++)
            System.out.print(str[i]);
         System.out.println("");
      }
   }
   public static void main(String[] args)
   {
      Scanner sc = new Scanner(System.in);
      String str = sc.next();
      printNearestNonDecreasing(str.toCharArray());
   }
}

The above code takes O(n) time and constant extra memory.