A number is tidy if its decimal digits never decrease from left to right (for example 1188 or 7). A ticket counter currently shows n. Return the largest tidy number that is <= n.
Examples
Input: n = 3321
Output: 2999
Input: n = 1234
Output: 1234
Explanation: 1234 is already tidy.
Input: n = 100
Output: 99
Constraints
0 <= n <= 10**18- Target complexity: O(d) where d is the number of digits.
Goals
- Find the first place where the digits stop being non-decreasing
- Decrement a digit and fill everything after it with 9s
- Propagate the fix leftwards when the decrement breaks an earlier pair