单调递增的数字（738）

题目

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）

示例

输入: N = 10 输出: 9

输入: N = 1234 输出: 1234

输入: N = 332 输出: 299

说明

N 是在 [0, 10^9] 范围内的一个整数。

算法

贪心算法

找到一个比当前数字小的最大的单调递增数字：当N[i]<=N[i+1]时，这个数的这两位满足单调递增；当N[i]>N[i+1]时，这两位不满足单调递增，我们需要将N[i]--，然后设N[i+1]=9，这样就能得到这两位单调递增的数字。我们将这个局部最优解扩大到全局最优就能得到不大于当前数字的单调递增数字

因为我们需要一个最大的递增数字，所以我们应该尽量修改靠后的位数（位数较低的数字），所以我们从后往前循环判断；当比较的两位不满足单调递增时，我们将高位数字-1，然后让高位之后的所有数字全部为9，这样我们就能得到一个不大于给定数字的单调递增数字了

export const monotoneIncreasingDigits = (N) => {
	if (N < 10) return N;
	const numbers = N.toString().split("");
	for (let i = numbers.length - 2; i >= 0; i--) {
		if (numbers[i] > numbers[i + 1]) {
			numbers[i]--;
			for (let j = i + 1; j < numbers.length; j++) {
				numbers[j] = 9;
			}
		}
	}
	return Number(numbers.join(""));
};