leetcode weekly contest 61 ( 738. Monotone Increasing Digits )

Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits.

(Recall that an integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.)

Example 1:
Input: N = 10
Output: 9
Example 2:
Input: N = 1234
Output: 1234
Example 3:
Input: N = 332
Output: 299
Note: N is an integer in the range [0, 10^9].

---

一些废话

好久没有更新了 ， 先更新题目，再把说好的rsa算法更新了

---

题目

那么先说题目给一个数N，找到小于N的最大的每位递增的数
看例子

e.g. 2147483647 
ans :1999999999

好理解题目意思了

---

分析

我们首先可以想到暴力枚举：可以看到e.g. 大int很容易超时

那么我们可以观察一下

分下情况
1.本身这个数就是递增的 直接返回这个数 这个没有疑问

2.先递增再递减 递增的部分可以留着把最后一位减一后补9（简单思考即可）

3.先递减再递增 e.g.987789
思考一下
我们可以选择哪些数
因为987789先递减 》》 9不能留了（ 很好理解吧，留了9 后面必须全为9）
所以第一位减1 变成 8
后面全填9即可
4.递减
和先递减没区别

这样总结发现》》找到第一个递减的数的前一位减1 然后填9 即可

---

代码

class Solution {
public:
    vector< int > num ; 
    void convert( int N ){
        while( N ){
            num.push_back( N%10 ) ;
            N/=10;
        }
        reverse( num.begin() , num.end() ) ;
    }
    int monotoneIncreasingDigits(int N) {
        convert( N );
        bool can = true ;
        int pos = 0 ;
        for( int i=1 ; i< num.size() ; i++){
            if( num[i] < num[i-1]){
                can = false ;
                pos = i-1 ;
                break ;
            }
        }
        int tmp = pos ;
        int target = num[pos];
        for( int i=tmp ; i>=0 ; i--){
            if( num[i] == target){
                pos = i ;
            }
        }
        if( can )
            return N;
        int ans = 0 ;
        for( int i=0 ; i<pos; i++){
            ans= ans*10+num[i];
        }
        ans = ans*10 + num[pos]-1;
        for( int i=pos+1 ; i<num.size() ; i++){
            ans= ans*10 +9 ;
        }
        return ans ;
    }
};

---

时间复杂度 $O(D)$

空间复杂度 $O(1)$