C++で単調増加する桁を持つ最大の数を求めるアルゴリズム

非負整数 N が与えられたとき、N 以下の数の中で「単調増加する桁」を持つ最大の数を求めることを考えます。ここで、ある整数が単調増加する桁を持つとは、隣り合うどの2桁 x と y についても x <= y が成り立つ場合を指します。例えば、入力が 332 の場合、答えは 299 となります。

この問題は、貪欲法（グリーディーなアプローチ）を使って効率的に解くことができます。基本的な考え方は、左から右へ桁を走査し、単調増加が崩れる位置を見つけたら、その直前の桁を1つ減らして、それ以降のすべての桁を 9 にするというものです。

解法の手順

• 数値 N を文字列 s に変換し、i := 1、n := s の長さとします。
• i < n かつ s[i] >= s[i - 1] の間、i を1ずつ増やします。これにより、単調増加が続いている範囲を特定できます。
• i < n の場合（＝単調増加が崩れる箇所が存在する場合）、i > 0 かつ s[i - 1] > s[i] の間、次の処理を繰り返します。
  • i を1減らす
  • s[i] を1減らす（桁を繰り下げる）
• j を i + 1 から n - 1 まで動かしながら、s[j] := '9' とします。
• 最後に s を数値に変換して返します。

C++での実装例

それでは、上記のアルゴリズムを実際にC++で実装してみましょう。コードを見ることで理解が深まります。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int monotoneIncreasingDigits(int N) {
      string s = to_string(N);
      int i = 1;
      int n = s.size();
      while(i < n && s[i] >= s[i - 1]) i++;
      if( i < n)
      while(i > 0 && s[i - 1] > s[i]){
         i--;
         s[i]--;
      }
      for(int j = i + 1; j < n; j++)s[j] = '9';
      return stoi(s);
   }
};
main(){
   Solution ob;
   cout << (ob.monotoneIncreasingDigits(332));
}

入力

332

出力

299

アルゴリズムのポイント

このアルゴリズムの計算量は O(n)（n は桁数）であり、非常に効率的です。重要なのは、単調増加が崩れた位置より前の桁も調整が必要な点です。例えば 332 の場合、「33」までは増加していますが「32」で崩れます。このとき、3番目の桁を減らすだけでは不十分で、前の桁との大小関係を保ちながら遡って調整する必要があります。そのため while ループで条件を満たす限り i を戻しながら桁を減算しています。最後に残りの桁をすべて 9 にすることで、N 以下の最大の単調増加数が得られます。