Monotone Increasing Digits

• Start a loop with a variable i initialized to n.
• In each iteration, check if the number i has monotone increasing digits.
• To perform the check, create a helper function isMonotone(num):
  • Convert num to its string representation, s.
  • Iterate through the string s from the first character to the second-to-last character.
  • If at any point s.charAt(j) > s.charAt(j+1), the number is not monotone, so return false.
  • If the loop completes without finding such a violation, return true.
• If isMonotone(i) returns true, then i is the largest monotone increasing number less than or equal to n. Return i.
• If not, decrement i and continue the loop.
• The loop will eventually terminate because 0 is a monotone increasing number.

The most straightforward way to solve this problem is to use a brute-force search. We start with the given number n and check if it satisfies the monotone increasing digit property. If it does, we have found our answer since we are looking for the largest number less than or equal to n. If it doesn't, we decrement the number by one and repeat the process. We continue this until we find a valid number. Since 0 is a valid monotone increasing number, this process is guaranteed to terminate.

A helper function can be used to check if a number is monotone increasing. This function would convert the number to a string or an array of digits and then iterate through them, ensuring that each digit is less than or equal to the next one.

Here is a code snippet for this approach:

1class Solution {2    public int monotoneIncreasingDigits(int n) {3        for (int i = n; i >= 0; i--) {4            if (isMonotone(i)) {5                return i;6            }7        }8        return 0; // Should not be reached for n >= 09    }10 11    private boolean isMonotone(int num) {12        String s = String.valueOf(num);13        for (int i = 0; i < s.length() - 1; i++) {14            if (s.charAt(i) > s.charAt(i + 1)) {15                return false;16            }17        }18        return true;19    }20}

• Convert the input integer n to a character array s.
• Initialize an integer marker to the length of s. This marker will point to the first digit (from the left) that needs to be changed to '9'.
• Iterate through the character array s from right to left, starting from the second to last digit (i = s.length - 2 down to 0).
• In each iteration, compare s[i] with s[i+1].
• If s[i] > s[i+1], a violation is found. This means the prefix ending at s[i] is too large.
  • To correct this, decrement the character s[i] by one.
  • Update marker to i + 1, as all digits from this position onwards must be '9' to maximize the resulting number.
• After the loop finishes, iterate from marker to the end of the array (j = marker to s.length - 1).
• Set s[j] to '9'.
• Finally, convert the modified character array s back to an integer and return it.

This greedy algorithm works by identifying the point of non-monotonicity and correcting it to form the largest possible valid number. We want to keep the most significant digits as large as possible, which means we want to preserve the prefix of n as much as we can.

We can process the digits of n as a character array. A right-to-left scan is particularly effective. We iterate from the end of the number towards the beginning. If we find a pair of adjacent digits s[i-1] and s[i] such that s[i-1] > s[i], we've found a "cliff". To make the number monotone, we must decrease s[i-1]. After decrementing s[i-1], all digits to its right should be set to '9' to make the resulting number as large as possible. The right-to-left scan naturally handles cases where decrementing a digit causes a new violation with the digit to its left (e.g., in 332, changing the second 3 to 2 makes the number 322, which is still not monotone).

For example, with n = 332:

1. s = ['3', '3', '2'].
2. Scan from right. At i=2, we compare s[1] and s[2]. 3 > 2 is a violation.
3. We decrement s[1] to '2'. The array becomes ['3', '2', '2']. We record that digits from index 2 onwards should be '9'.
4. Continue scan. At i=1, we compare s[0] and s[1]. Now 3 > 2 is a violation.
5. We decrement s[0] to '2'. The array becomes ['2', '2', '2']. We update our record: digits from index 1 onwards should be '9'.
6. After the scan, we apply the change: set digits from index 1 to the end to '9'. The array becomes ['2', '9', '9'].
7. The result is 299.

Here is the code for this approach:

1class Solution {2    public int monotoneIncreasingDigits(int n) {3        char[] s = String.valueOf(n).toCharArray();4        int len = s.length;5        int marker = len;6        // Scan from right to left to find the first cliff7        for (int i = len - 1; i > 0; i--) {8            if (s[i] < s[i - 1]) {9                // Decrement the digit at the cliff10                s[i - 1]--;11                // Mark the starting position for filling with 9s12                marker = i;13            }14        }15        // Fill all digits from the marker to the end with '9'16        for (int i = marker; i < len; i++) {17            s[i] = '9';18        }19        return Integer.parseInt(new String(s));20    }21}