738. 单调递增的数字

[bt2ee]

题目

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）

示例

示例 1:

输入: N = 10
输出: 9

示例 2:

输入: N = 1234
输出: 1234

示例 3:

输入: N = 332
输出: 299

解题

这个题开始没有想出来解决办法，是看到了题解后才写出来的。

• 循环一轮。查找递增的 index
• index 右边全部替换成 9
• index 左边 -1 然后继续递归出正确的数字
• string 拼接

解题方法

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var minSubsequence = function(nums) {
  nums.sort((a, b) => b - a)
  const sum = nums.reduce((pre, cur) => pre + cur, 0) / 2
  const result = []
  let curSum = 0
  for (let i = 0; i < nums.length; i++) {
    if (curSum + nums[i] > sum) {
      result.push(nums[i])
      return result
    } else {
      result.push(nums[i])
    }
    curSum += nums[i]
  }
  return result
};