17. 单调递增的数字（738）

一、题目内容 中等

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

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

示例1：

输入: n = 10 输出: 9

示例2：

输入: n = 1234 输出: 1234

示例3：

输入: n = 332 输出: 299

二、解题思路

例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增）。
首先想让strNum[i - 1]--，然后strNum[i]给为 9，这样这个整数就是 89，即小于 98 的最大的单调递增整数。
这一点如果想清楚了，这道题就好办了。

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

全局最优：得到小于等于N的最大单调递增的整数。
但这里局部最优推出全局最优，还需要其他条件，即遍历顺序，和标记从哪一位开始统一改成 9。
此时是从前向后遍历还是从后向前遍历呢？
332，从前向后遍历的话，那么就把变成了 329，此时 2 又小于了第一位的 3 了，真正的结果应该是299
所以从前后向遍历会改变已经遍历过的结果！很麻烦

从后往前遍历，就可以重复利用上次的比较结果，332——>329——>299。
我们不应该在 3 > 2 的时候，就把 2 改成 9，而是找到后面需要改成 9 的起始位置。
为什么意思呢？我们举个例子：500
从后往前遍历，我们用 flat 来表示从这个位置开始，需要把后面的值都改成 9。

1. 遇到 0，和前面的 0 比较，不需要修改。继续往前
2. 遇到 0，和前面的 5 比较，需要修改，把 5 变成 4，然后 flat = 1，表示这个 0 的索引

然后现在的数为 400，从 flat 的位置开始，把后面的值都改为 9。400 ——> 499

如果我们不是找 flat 起始位置，修改后面的值，
而是直接遇到 i 的值 小于 i - 1 的值，然后去将 i -1 的值减一，i 的值变为 9，我们来看看 500 会发生什么

1. 遇到 0 不小于前面的 0，继续往前
2. 遇到 0 小于前面的 5，5 变为 4，0 变为 9

结果 490，并不是期望的 499。

三、具体代码

/**
 * @param {number} n
 * @return {number}
 */
var monotoneIncreasingDigits = function (n) {
  const str = n.toString()
  const result = str.split('').map(a => Number(a))
  let flat = Infinity
  for (let i = str.length - 1; i > 0; i--) {
    if (result[i - 1] > result[i]) {
      result[i - 1] -= 1
      flat = i
    }
  }
  for (let i = flat; i < str.length; i++) {
    result[i] = 9
  }
  return Number(result.join(''))
};

四、其他解法