C++での単調増加桁数

非負の整数Nがあるとすると、単調に増加する桁でN以下の最大数を見つける必要があります。隣接する数字のxとyの各ペアがx<=yを満たす場合にのみ、整数の数字が単調に増加することがわかっています。したがって、入力が332の場合、結果は299になります。

これを解決するには、次の手順に従います-

• s：=文字列としてのN、i：=1、n：=sのサイズ
• while i =s [i – 1]
  • iを1増やします
• if i
• i>0かつs[i– 1]> s [i]の場合、
  • iを1つ減らします
  • s[i]を1つ減らします

理解を深めるために、次の実装を見てみましょう-

例

#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