力扣（单调递增的数字）

738. 单调递增的数字

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

思路：

对于x和y，如果x>y,则令x-1，y以及后面的数字都变成9，这样就是在不大于该数字的情况下的最大的数字。特殊情况：若形式上有--------xxxxxy---，此时x>y，如果把和y相邻的x变小，则前面会出现xxxx（x-1）99999----，则又出现了不符合的情况，因此应该把最前面的x减小一，把后面的数字都变成9.之所以最前面的数字减小1以后仍然满足条件，是因为此处的是相同数字里最前面的一个，在它之前的数字一定是小于它不能是等于它，因此减一以后最多是等于不会是小于，所以可以。

class Solution {
public:int monotoneIncreasingDigits(int n) {//不匹配的时候，减一变九if(n==0)return 0;vector<int>ap;int n1=n;while(n1>0){ap.push_back(n1%10);n1/=10;}for(int i=ap.size()-1;i>=1;i--){if(ap[i]>ap[i-1]){   //找到相同数字里最前面那个位置,因为可能存在连续相同数字，减一以后前面不满足关系，但是相同数字最前面那个减一，仍然是符合关系的，因为是相同的最前面的一个，因此和其前面的一定是小于关系，减一最差也是等于，不会出现大于，因此可以while(i+1<ap.size()&&ap[i]==ap[i+1])i++;for(int j=0;j<i;j++)ap[j]=9;ap[i]--;break;}}n1=0;for(int i=ap.size()-1;i>=0;i--){n1=n1*10+ap[i];}return n1;}
};