最大數字非降序數字

Question

什麼是最大的正整數（稱爲k）小於或等於N，使得整數k的所有數字都是非遞減的？

限制條件：
= Ñ < = 10^18
= K < = N
時間限制：秒

解決的辦法之一是檢查所有從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。