Leetcode 738.单调递增的数字

题目：738.单调递增的数字

初始思路

没有思路

代码

  1. var monotoneIncreasingDigits = function (n) {
  2.     n = n.toString() // 数字转为字符串，方便使用下标
  3.     n = n.split('').map(item => {
  4.         return parseInt(item) // 转为数组
  5.     })
  6.     let flag = Infinity // 标记从哪位开始要变成9
  7.     for (let i = n.length - 1; i > 0; i--){
  8.         if (n[i - 1] > n[i]) {
  9.             //前一个大于后一位,前一位减1，后面的全部置为9
  10.             flag = i
  11.             n[i - 1]--
  12.             n[i] = 9
  13.         }
  14.     }
  15.     // 从标记位一直到最后都改成9
  16.     for (let i = flag; i < n.length; i++){
  17.         n[i] = 9
  18.     }
  19.     n = n.join('')
  20.     return parseInt(n)
  21. };

感想

  1. 局部最优：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]—，然后strNum[i]给为9，可以保证这两位变成最大单调递增整数。全局最优：得到小于等于N的最大单调递增的整数。
  2. 思路很精妙，多看看讲解。