JavaScriptで単調増加する桁を持つ、指定した数以下の最大の数を求める方法

単調増加する桁（Monotonically Increasing Digits）とは

整数が「単調増加する桁」を持つとは、隣り合う任意の2つの桁 x と y の間に、常に x <= y が成り立つことを指します。たとえば 1234 や 2299 は左から右へ向かって桁が増加（または同じ）ため条件を満たしますが、332 のように「3 → 3 → 2」と減少が含まれる数は単調増加とはみなされません。

問題

今回求められているのは、数値 num を第一引数（かつ唯一の引数）として受け取るJavaScript関数を記述することです。

この関数は、num 以下の数の中から、単調増加する桁を持つ最大の数を見つけて返す必要があります。

たとえば、関数への入力が次の場合を考えてみましょう。

入力

const num = 332;

出力

const output = 299;

332 以下で単調増加となる最大の数は 299 です。332 や 330、321 などは途中で桁が減少するため、条件を満たしません。

解法のアプローチ

この問題は、次の手順で解くことができます。

1. まず、元の数 num 自体がすでに単調増加していれば、そのまま返します。
2. そうでない場合は、各桁について「その桁を1つ減らし、それ以降の桁をすべて9に置き換えた数」を候補として生成します。
3. 生成した候補が単調増加しているかどうかを検証し、条件を満たすものの中で最大の値を答えとして返します。

サンプルコード

以下が実際のコードです。

const num = 332;
const monotoneIncreasingDigits = (num) => {
   const checkMonotone = (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 (checkMonotone(num)) {
      return num
   }

   const digits = num.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 (checkMonotone(current)) {
            return Math.max(
            acc,current)
         }
      }
      return acc
   }, 0)
}
console.log(monotoneIncreasingDigits(num));

コードの解説

checkMonotone 関数は、引数として渡された整数が単調増加しているかどうかを判定するヘルパー関数です。数値を下の桁から順に取り出しながら、隣接する桁同士を比較していきます。1桁でも増加が崩れている箇所が見つかれば即座に false を返し、最後まで確認できれば true を返します。

本体の処理では、まず入力値そのものが条件を満たしていないかをチェックします。満たしていない場合は、数値を文字列として分解した各桁に対して reduce によるループを行い、「対象の桁を1減らして残りの桁をすべて9で埋めた候補値」を順番に生成します。各候補が単調増加であるかを検証しながら最大値を更新していくことで、num 以下かつ単調増加となる最大の数を効率的に特定できます。

出力

上記のコードを実行すると、コンソールには次の結果が出力されます。

299