给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
示例 1:
输入: N = 10 输出: 9
示例 2:
输入: N = 1234 输出: 1234
示例 3:
输入: N = 332 输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。
题目要求：找到不大于N的数， 这个数要求从高位到地位是递增的
思路：从高位找到第一位不满足要求的数，将其位置记为i，把i位的数字减小1， 且i位之后的数字要均为9，才能保证数字最大。 此外还要保证修改i位的数字后，要保证i之前的数字均保证满足递增的要求；就有一下几种情况
- i是最高位，将其减一即可
- i不是最高位，且a[i]-a[i+1]>=1, 直接把a[i]-1, 这种情况下依然满足递增的条件
- i不是最高位，且a[i]-a[i+1]<1, 此时a[i]-1<a[i+1], 这种情况下i位之前的数不再满足递增的条件。需要按照前面的分析继续向前查找，直到满足1或者2的条件
1 class Solution { 2 public: 3 vector<int> getnum(int n){ 4 vector<int> ans; 5 while(n){ 6 ans.push_back(n%10); 7 n /= 10; 8 } 9 return ans; 10 } 11 int monotoneIncreasingDigits(int N) { 12 vector<int> ans = getnum(N);//取得N的每一位数 13 bool flag = true; 14 int i; 15 for(i=ans.size()-1; i>=1; i--){ 16 if(ans[i]>ans[i-1]){ 17 flag = false; 18 break; 19 } 20 } 21 if(flag) return N;//N本身就是递增的，直接返回 22 if(i==ans.size()-1) ans[i]--;//情况1 23 else { 24 int m = i; 25 while(m<ans.size()-1 && ans[m]-ans[m+1]<1){//情况3，直到满足条件1，或者2就退出 26 ans[m]=9; 27 m++; 28 } 29 ans[m]--;//情况2 30 } 31 for(int k=i-1; k>=0; k--) ans[k]=9;//i位之后的数字全部置为9，保证数字最大 32 int temp=0; 33 for(i = ans.size()-1; i>=0; i--) 34 temp = temp*10 + ans[i]; 35 return temp; 36 } 37 38 };
一些小改进
把上面的情况3在一个循环中解决，小小的精简了一下代码
1 class Solution { 2 public: 3 vector<int> getnum(int n){ 4 vector<int> ans; 5 while(n){ 6 ans.push_back(n%10); 7 n /= 10; 8 } 9 return ans; 10 } 11 int monotoneIncreasingDigits(int N) { 12 vector<int> ans = getnum(N); 13 int begin=-1, temp=0; 14 for(int i=0; i<ans.size()-1; i++){ 15 if(ans[i]<ans[i+1]){ 16 ans[i+1] = ans[i+1]-1; 17 begin = i; 18 } 19 } 20 for(int k=begin; k>=0; k--) ans[k]=9; 21 for(int i = ans.size()-1; i>=0; i--) 22 temp = temp*10 + ans[i]; 23 return temp; 24 } 25 };
这种问题，把N转换成字符串是最为简便的，不用去单独获取N的每一位数。