Monotone Increasing Digits

I had tried solving this problem few years back, failed. Took a look at the hint, and if you follow the hint, you'll solve it too. Here is the problem: 

Monotone Increasing Digits - LeetCode

738. Monotone Increasing Digits

Medium

An integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.

Given an integer n, return the largest number that is less than or equal to n with monotone increasing digits.

 

Example 1:

Input: n = 10
Output: 9

Example 2:

Input: n = 1234
Output: 1234

Example 3:

Input: n = 332
Output: 299

 

Constraints:

• 0 <= n <= 109

Accepted

34,146

Submissions

73,531

And here was the hint: "Build the answer digit by digit, adding the largest possible one that would make the number still less than or equal to N."

This is exactly how the solution was implemented. Since we're looking at the increasing sequences only, it doesn't take a long time to converge. Code is below, cheers, ACC.

public int MonotoneIncreasingDigits(int n)
{
    long retVal = 0;
    MonotoneIncreasingDigits(n, -1, ref retVal);
    return (int)retVal;
}

private void MonotoneIncreasingDigits(long n,
                                        long currentNumber,
                                        ref long retVal)
{
    if (currentNumber > n) return;

    if (currentNumber > 0) retVal = Math.Max(retVal, currentNumber);

    if (currentNumber == -1)
    {
        for (int i = 9; i > 0; i--) MonotoneIncreasingDigits(n, i, ref retVal);
    }
    else if (10 * currentNumber <= n)
    {
        long d = currentNumber % 10;
        for (long i = 9; i >= d; i--)
        {
            MonotoneIncreasingDigits(n, 10 * currentNumber + i, ref retVal);
        }
    }
}