738. 单调递增的数字

题目

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

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

示例

输入: N = 10
输出: 9

输入: N = 1234
输出: 1234

输入: N = 332
输出: 299

说明: N 是在 [0, 10^9] 范围内的一个整数。

题型归类: 循环

思路一

我们要做的是找到小于等于N的最大整数,然后这个整数是从坐到右递增的,也就是从高位到低位递增。

因为我们一开始,无法直接知道数字的长度,如果要知道又要多一次循环,我想一次循环解决这个问题,那么我们从低位开始,一个数字一个数字获取,如果相邻的数字分别为abcde, 那么首先获取e和d,比较e和d的大小。

如果 d <= e, 那么满足条件,继续比较后面的d和c;
如果 d > e, 那么e需要重置为9,d减1,然后再继续比较后面的d和c(e重置为9是保持数字最大化中最近的一个数字);
如果在比较到 a 和 b的时候,发现 a > b,那么就要b开始全部重置为9,a减1;
到了最后一位,因为我们是按顺序计算着来的,最后一位就看是否发生了减1的行为;

这里面有一种特殊情况,就是例如100, 101, 之类的数字,就是取数相邻两个数字的时候,当前数字为0,一旦遇到有0,那么表示高位数字一定会比当前数字大,那么就还要从当前数字开始,全部重置为9,并且高位-1;

// 代码实现

impl Solution {
    /// author arlicle
    /// https://www.debugmyself.com
    /// https://github.com/arlicle
    pub fn monotone_increasing_digits(n: i32) -> i32 {
        let mut n = n;
        let mut result = 0;
        let (mut n, mut result, mut index, mut extra_sub) = (n, 0, 0, 0);
        while n > 0 {
            let mut right_num = n % 10 - extra_sub;
            n = n / 10;
            let left_num = n % 10;
            if (n == 0) {
                // n等于0,表示是最后一位数字了 不用进行任何操作
            } else if right_num >= left_num && right_num != 0 {
                // 后一个数字 大于等于前一个数字
                extra_sub = 0;
            } else {
                // 重置数字为9
                result = 10_i32.pow(index) - 1;
                right_num = 9;
                extra_sub = 1;
            }
            result += right_num * 10_i32.pow(index);
            index += 1;
        }
        result
    }
}


#[cfg(test)]
mod test {
    use crate::Solution;

    #[test]
    pub fn monotone_increasing_digits_test() {
        assert_eq!(99, Solution::monotone_increasing_digits(100));
        assert_eq!(99, Solution::monotone_increasing_digits(101));
        assert_eq!(1234, Solution::monotone_increasing_digits(1234));
        assert_eq!(0, Solution::monotone_increasing_digits(0));
        assert_eq!(899999, Solution::monotone_increasing_digits(989998));
    }
}

leetcode执行结果

执行用时 : 0 ms , 在所有 Rust 提交中击败了 100.00% 的用户
内存消耗 : 2 MB , 在所有 Rust 提交中击败了 100.00% 的用户

可以看到执行效率很高,几乎为0ms,循环的次数和数字的长度是一样的,算法复杂度是$O(n)$。其实这样又是从外到内的,同样可以使用递归来解决。

leetcode相似题型

移掉K位数字

2019-09-25 07:40

留言