【LeetCode】738. 单调递增的数字

738. 单调递增的数字

知识点:字符串;贪心

题目描述

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

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

示例
输入: N = 10
输出: 9

输入: N = 1234
输出: 1234

输入: N = 332
输出: 299


解法一:贪心

想一下这个过程,如果比前一位大的话那就可以不用动直接返回;如果比前一位小的话例如98,应该怎么做呢,我们取小于等于8的都没用,因为都比前一位要小,不满足递增,所以只能让前一位变小一位了,9变成8,那我们最后一位自然要取到9,高位数和这个二位数一个道理,只要有比前一位小的了,那自然要把前一位-1,后面所有位变为9;

但是还有一点要注意,比如332,我们找到2小了,那把前一位减1了,但是减完之后自己又比更前一位的小了,所有更前一位也得减1;只要自己前面减1了,那自己就不用管了,赋成9就行,所以还要找到减完之后仍然满足递增的那个位置;

所以这道题是在找两个位置

  • 往后找:第一个比前一位小的位置;
  • 往前找:往前开始-1后第一个仍然满足递增的位置;
class Solution {
    public int monotoneIncreasingDigits(int n) {
        char[] str = Integer.toString(n).toCharArray();  //转换成字符数组方便操作,注意这个方法;
        int i = 1;
        while(i < str.length && str[i] >= str[i-1]){
            i++;  //往后找:找到第一个比前一位小的元素;
        }
        if(i < str.length){
            while(i > 0 && str[i] < str[i-1]){
                str[i-1]--; //往前找:前一位-1后可能又比更前一位小了,所以循环往前找到满足递增的;
                i--;
            }
            for(i += 1; i < str.length; i++){
                str[i] = '9';  //后面全是9就可以了;
            }
        }
        return Integer.parseInt(new String(str)); //字符数组转成字符串,再转成数组;
    }
}

体会

要学会整形转字符串,转字符数组:Integer.toString(n).toCharArray();
要学会字符数组转字符串,转整形:Integer.parseInt(new String(str));

上一篇:leetcode 738. 单调递增的数字


下一篇:738单调递增的数组和290单词规律