贪心策略,从左到右,从高位到低位不断的分析数字,如果当前位是属于上升段,那么不断向右移动。如果移动到最右端,当前数字满足要去。
若否,那么将前一位-1,看看前一位是否满足要求,如果已经满足要求,那么将后面的位全部变为9,即得到满足要求的答案。
如果当前位-1不满足递增要求,说明要继续向前判断,直到满足要求后,将后面的所有位都变为9.
class Solution {
public:
int monotoneIncreasingDigits(int N) {
string s = to_string(N);
int n = s.size(), i = 1;
while(i<n&&s[i]>=s[i-1]){
i++;
}
if(i==n) return N;
while(i>0&&s[i]<s[i-1]){
s[i-1]--;
i--;
}
i++;
while(i<n){
s[i++] = '9';
}
return stoi(s);
}
};