738. Monotone Increasing Digits

Solution idea

Greedy

• 如果input number不符题意, 从后往前, 前一个digit - 1, 当前digit变成9

• 局部最优：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]--，然后strNum[i]给为9，可以保证这两位变成最大单调递增整数。

• 全局最优：得到小于等于N的最大单调递增的整数。

Time complexity = $O(n^2)$

Resource

代码随想录-738.单调递增的数字