Leetcode 738 - Monotone increasing digits

Note:

• By our brute force solution, if we try several nums, it’s easy to find that if nums[i-1] < nums[i], we only need to make digits after i become 9, then subtract 1 from nums[i-1] (If there is no same digits proceeding it).
• For example, 7886213 -> 7799999, we need to make the first 8 as 7, not the second.

Question
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

Code:

Brute force

Greedy