580. Never Going Down Digits
A locker uses numeric codes that are only accepted when their digits never decrease from left to right, for example 1558 or 3999, while 1230 and 4210 are rejected. Repeated digits are fine. A technician has an upper limit n printed on the locker and needs the strongest accepted code that does not exceed it.
Return the largest integer x such that 0 <= x <= n and the decimal digits of x are in non-decreasing order. Leading zeros are not written, so a single digit such as 7 is always accepted, and 0 is accepted.
Counting down from n until an accepted code appears can take about a billion steps, which is too slow. Solve it directly from the digits in O(d) time, where d is the number of digits, using O(d) space.
Example 1
- Input:
- n = 4210
- Output:
- 3999
- Explanation:
Lowering the 4 to 3 makes the remaining digits free, so they all become 9, giving 3999.
Example 2
- Input:
- n = 1357
- Output:
- 1357
- Explanation:
The digits already never decrease, so the answer is n itself.
Example 3
- Input:
- n = 7000
- Output:
- 6999
- Explanation:
The 7 must drop to 6 and the rest become 9, giving 6999.
Constraints
0 ≤ n ≤ 1000000000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(d)
- Space
- O(d)