力扣738-单调递增的数字


力扣738-单调递增的数字

一、原题题目

1.1 题目

​ 给定一个非负整数 N,找出小于或等于N的最大的整数,同时这个整数需要满足其各个位数上的数字是单调递增。

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

1.2 示例

  • 示例1:

    输入:N = 10
    输出:9

  • 示例2:

    输入:N = 1234
    输出:1234

  • 示例3:

    输入:N = 332

    输出:299

  • 说明:N 是在[0, 109]范围内的一个整数。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/monotone-increasing-digits

二、解题思路

2.1 题目意思理解

​ 按照题目意思,我们从前往后去分析数据,如果当前位数上的值小于后一位的值时,那么当前位值要 -1,右边的所有位置 9 。否则按照位数向右递归。

2.2 详细代码(Java)

public class Solution {
    public int monotoneIncreasingDigits(int N) {
        // 将 int 转换成字符串再转换成字符数组 
       char[] strN = Integer.toString(N).toCharArray();     
       int i = 1;
        // 找到前一个数值大于当前数值的位置
       while (i<strN.length && strN[i-1]<=strN[i])  i++;
        // 原数字不是单调递增的
       if (i<strN.length){
           // 前一个数值大了,执行减一操作,减一后要检验之前的
           while (i > 0 && strN[i-1]>strN[i]){
               strN[i-1]--;
               i--;
           }
           // 讲最终修改后的位置之后都改为 9
           for (i+=1;i<strN.length;i++) strN[i]='9';        
       }
        return Integer.parseInt(new String(strN));
    }
}

2.3 算法执行结果

算法执行结果

三、总结分析

​ 从前往后遍历,如果前面的值大于后面的值就把当前位数减一然后把后面的值变成9,以此类推


文章作者: ItDaChuang
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ItDaChuang !
评论
 上一篇
力扣290-单词规律 力扣290-单词规律
给定一种规律 pattern 和一个字符串 str ,判断 str 是否遵循相同的规律。这里的遵循指完全匹配,例如, pattern 里的每个字母和字符串 str 中的每个非空单词之间存在着双向连接的对应规律。
2020-12-16
下一篇 
力扣649-Dota2参议院 力扣649-Dota2参议院
Dota2 的世界里有两个阵营:Radiant (天辉)和 Dire(夜魇)。Dota2 参议院由来自两派的参议员组成。现在参议院希望对一个 Dota2 游戏里的改变作出决定。他们以一个基于轮为过程的投票进行。在每一轮中,每一位参议员都可以行使两项权利中的一项...
2020-12-11
  目录