小于或等于 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)。
最佳答案
一个简单的贪婪方法是从右边扫描数字,如果你发现一个数字小于它左边的数字,那么将左边的数字减 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
。
关于algorithm - 具有非递减数字的最大数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43331084/