假设我们有一个非负整数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