738单调递增的数字 · Kaige Dong's Site

题目类型

贪心算法

思路

暴力递减：时间超出限制。写一个判断是否为单调递增的函数，如果是，返回，如果不是，原数字减1：

结果时间太久了，测试用例有很多大数字。

时间复杂度：??

impl Solution {
    pub fn monotone_increasing_digits(n: i32) -> i32 {
        let mut t = n;
        while ! Self::is_good(t) {
            t -= 1;
        }
        return t;
    }

    pub fn is_good(n: i32) -> bool {
        let mut remainder = n % 10; // 余数
        let mut rest = n / 10; // 去掉余数的数

        while rest > 0 {
            if remainder < rest % 10 {
                return false;
            }
            remainder = rest % 10;
            rest = rest / 10 ;
        }
    
        return true;
    }
}

因为要找最大的符合条件的数，直观上要依次递减，判断是否符合。从前往后判断，找到第一个不满足的位置。

例如数字4554321, 很容易找到，中间的54开始不满足，则从4554321 直到4550000 都不满足。这一部分不用判断，可以直接将数字变成4550000，这样就跳过了很多次判断。

然后，4550000 再递减，减去 1高位退位，为 4549999，不满足，还要一直递减。直到减去1不退位，即最后的数字大于前一个数字退位才不会比前一个数小 (相比之下450000减去1 为449999满足)。这一段相当于，出现4550000 则直接变成4500000即可，这样减去1刚好是最大的符合条件的数。

上面两步的例子：

例1：
对于123454321：
从前往后遍历1：找到54中的4不满足，将4及后面变成0；结果为 123450000
从最后一个5往前遍历：找是否前面有等于5的数，如果有将5变成0：发现没有，结果为 123450000
然后减1，即为结果：123449999

例2：
对于数字
1234554321：
从前往后遍历1：找到54中的4不满足，将4及后面变成0；结果为 1234550000
从最后一个5往前遍历：找是否前面有等于5的数，如果有将5变成0：结果为：1234500000
然后减去1，即为结果：1234499999

时间复杂度：与数字的位数有关??。O(len(n))

pub fn is_good(n: i32) -> bool {
    let n_char_vec: Vec<char> = n.to_string().chars().collect();

    // 是一位数
    if n_char_vec.len() == 1 {
        return true
    }
    // 两位数及以上
    for i in 0..n_char_vec.len()-1 {
        if n_char_vec[i+1] < n_char_vec[i] {
            return false;
        }
    }
    return true;
}

pub fn monotone_increasing_digits(n: i32) -> i32 {

    if Self::is_good(n) { return n; }     // 符合要求，直接返回：

    // 否则转为Vec<char>进行迭代
    let mut num_vec: Vec<char> = n.to_string().chars().collect();
    let vec_len = num_vec.len();

    let mut i: usize = 0; // 指针，从数字的第0位开始

    while i < vec_len - 1 {
        if num_vec[i] > num_vec[i+1] {
            // 找到一个数字后的数字比它小的，并将该数字之后的全变成0
            for index in (i + 1)..vec_len {
                num_vec[index] = '0';
            }

            // 然后倒着查看，i之前的是否与i相同，如果相同，将i变为0. i == 0 时是满足的，即10000
            while i >= 1 && num_vec[i] == num_vec[i-1] {
                num_vec[i] = '0';
                i -= 1;
            }
        }
        i += 1; // i位置小于等于i+1时，i往后移一位
    }

    // 转为数字并减1返回
    let out: String = num_vec.into_iter().collect();
    let mut out: i32 = out.parse().unwrap();
    return out-1;
}

// 测试
assert_eq!( monotone_increasing_digits(10), 9);
assert_eq!( monotone_increasing_digits(1234), 1234);
assert_eq!( monotone_increasing_digits(332), 299);
assert_eq!( monotone_increasing_digits(614031667), 599999999);

Leetcode 结果：

执行用时	内存消耗	语言
0 ms	1.9 MB	Rust

Tips

Vec转String，String转i32：

let out: String = num_vec.into_iter().collect();
let mut out: i32 = out.parse().unwrap();

break 'outer 标记的使用：跳出指定位置

Leetcode 中相似的题型

122.买卖股票的最佳时机II

860.柠檬水找零

874.模拟行走机器人