Monotone Increasing Digits

Description

Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits.

(Recall that an integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.)

Example 1:

Input: N = 10
Output: 9

Example 2:

Input: N = 1234
Output: 1234

Example 3:

Input: N = 332
Output: 299

Note: N is an integer in the range [0, 10^9].

Solution(javascript)

/*
 * @lc app=leetcode id=738 lang=javascript
 *
 * [738] Monotone Increasing Digits
 */

// @lc code=start
/** Binary Search 不行！
 * @param {number} N
 * @return {number}
 */
const monotoneIncreasingDigits = function (N) {
  const isMonotone = (x) => {
    if (x <= 9) {
      return true
    }
    let currentDigit = x % 10
    while (x) {
      const next = Math.floor(x / 10)
      const nextDigit = next % 10
      if (currentDigit >= nextDigit) {
        currentDigit = nextDigit
        x = next
      } else {
        return false
      }
    }
    return true
  }
  if (isMonotone(N)) {
    return N
  }
  // 一次拿出来两个
  const digits = N.toString().split('').map(x => Number(x))
  return digits.reduce((acc, num, index) => {
    if (num >= 1) {
      const current = parseInt(digits.slice(0, index).join('') + num - 1 + new Array(digits.length - index - 1).fill('9').join(''), 10)
      if (isMonotone(current)) {
        return Math.max(
          acc,
          current,
        )
      }
    }
    return acc
  }, 0)
}
// @lc code=end