738. 单调递增的数字-深度优先遍历方法

738. 单调递增的数字

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

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

示例 1:

输入: n = 10
输出: 9

示例 2:

输入: n = 1234
输出: 1234

示例 3:

输入: n = 332
输出: 299

这题博主做法也是很有新意，感兴趣可以学习一下，解题代码如下：

int length(int n,int *re){
    int len=0;
    while(n){
        re[len]=n%10;
        n=n/10;
        len++;
        
    }
    return len;
}
void reverse(int *re,int len){
     for(int i=0;i<len/2;i++){
        int t=re[i];
        re[i]=re[len-i-1];
        re[len-i-1]=t;
       
    }

}
int find;
void dfs(int *re,int len,int now_pos,int pre,int *re_s,long long now_val,long long targe_val){
  
    if(now_pos==len){
        find=1;
    }
    if(find==0){
        int i;
        if(now_val<targe_val){
            i=9;
        }
        else{
            i=re[now_pos];
        } 
       
    
        for(;i>=0;i--){
            if(i>=pre&&find==0){
                re_s[now_pos]=i;
                 now_val=now_val*10+i;

                targe_val=targe_val*10+re[now_pos];
                
                dfs(re,len,now_pos+1,i,re_s,now_val,targe_val);

            }
        }

    }

}
int monotoneIncreasingDigits(int n){
    int *re=(int *)malloc(sizeof(int)*10);
    int *re_s=(int *)malloc(sizeof(int)*10);
    int len=length(n,re);
    reverse(re,len);
    find=0;
    int re_ts=0;
     dfs(re,len,0,-1,re_s,0,0);
      for(int i=0;i<len;i++){
          re_ts=re_ts*10+re_s[i];
       
    }
   

    
    

    return re_ts;


}