C++刷leetcode（738. 单调递增的数字）【数学】

糖逗

题目描述：

1. 给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
   
2. 
   
3. （当且仅当每个相邻位数上的数字&#160;x&#160;和&#160;y&#160;满足&#160;x <= y&#160;时，我们称这个整数是单调递增的。）
   
4. 
   
5. 示例 1:
   
6. 
   
7. 输入: N = 10
   
8. 输出: 9
   
9. 示例 2:
   
10. 
    
11. 输入: N = 1234
    
12. 输出: 1234
    
13. 示例 3:
    
14. 
    
15. 输入: N = 332
    
16. 输出: 299
    
17. 说明: N&#160;是在&#160;[0, 10^9]&#160;范围内的一个整数。
    
18. 
    
19. 来源：力扣（LeetCode）
    
20. 链接：https://leetcode-cn.com/problems/monotone-increasing-digits
    
21. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. public:
   
3.     bool valid(string& input){
   
4.         int len = input.size();
   
5.         if(len == 1)return true;
   
6.         for(int i = 1; i < len; i++){
   
7.             if(input[i-1] > input[i]) return false;
   
8.         }
   
9.         return true;
   
10.     }
    
11.     int monotoneIncreasingDigits(int N) {
    
12.         string store = to_string(N);
    
13.         int len = store.size();
    
14.         if(valid(store))return N;
    
15.         string temp;
    
16.         int leave;
    
17.         bool flag = false;
    
18.         for(int i = 0; i < len; i++){
    
19.             temp += store[i];
    
20.             if(!valid(temp)){
    
21.                 temp = temp.substr(0, temp.size() - 1);
    
22.                 if(temp.size() >= 2 && temp[temp.size() - 1] == temp[temp.size() - 2])flag = true;
    
23.                 leave = len - i;
    
24.                 break;
    
25.             }
    
26.         }
    
27.         int res;
    
28.         if(flag == true){
    
29.             int num = 1;
    
30.             int temp2 = temp.size();
    
31.             for(int i = temp2 -1; i >= 1; i--){
    
32.                 if(temp[i] == temp[i-1])num++;
    
33.                 else break;
    
34.             }
    
35.             for(int i = 1; i < num; i++){
    
36.                 temp[temp.size() - i] = '9';
    
37.             }
    
38.             
    
39.             temp[temp.size() - num] = temp[temp.size() - num] - 1;
    
40.             res = stoi(temp);
    
41.         }else{
    
42.             res = stoi(temp) - 1;
    
43.         }
    
44.         
    
45.         for(int i = 0; i < leave; i++){
    
46.             res = res * 10 + 9;
    
47.         }
    
48. 
    
49.         return res;
    
50. 
    
51.     }
    
52. };

复制代码