C ++中的单调递增数字

假设我们有一个非负整数N,我们必须找到单调递增数字,该数字小于或等于N。我们知道,且仅当每对相邻数字的x和y满足x <= y时,整数才具有单调递增数字。)因此,如果输入为332,则结果将为299。

为了解决这个问题,我们将遵循以下步骤-

  • s:= N作为字符串,i:= 1,n:= s的大小

  • 而我<n和s [i]> = s [i – 1]

    • 使我增加1

  • 如果我<n

    • 将我减少1

    • 将s [i]减少1

    • 当i> 0且s [i – 1]> s [i]时,

  • 对于范围i +1至n的j

    • s [j]:='9'

  • 返回s作为数字

让我们看下面的实现以更好地理解-

示例

#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