algorithm - 具有非递减数字的最大数

Question

小于或等于 N 的最大正整数(称为 k)是多少，使得整数 k 的所有数字都是非递减顺序？

约束:
1 <= N <= 10^18
1 <= k <= N
时间限制:8 秒

其中一个解决方案是检查从 N-1 开始的所有值(即 N-1、N-2、N-3、......)，直到我找到数字不递减的数字。
但这只有在 N <= 10^10 时才能在给定的时间限制内完成。
它超过了给定约束的时间限制 (N <= 10^18)。

Answer 1

一个简单的贪婪方法是从右边扫描数字，如果你发现一个数字小于它左边的数字，那么将左边的数字减 1 并替换所有9 从当前数字到最右边的数字。

例如:

132 -> 1 3 2

2 < 3 so replace 2 by 9 and decrease 3 by 1

您可以这样做，因为生成的数字肯定会小于原始数字。而且我们还想最大化数字，所以我们用最大可能的数字 9 替换数字，并用最小可能的数字 1 减少左边的数字，以最大化结果数字.

对左侧的所有数字重复此过程，直到找到有效数字。是的，检查极端情况(前导零)。

对于数字 1332

1332 -> 1329 -> 1299(有效号码)

所以答案将是 1299。