给定一个非负整数 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));
}
}
执行用时 : 0 ms , 在所有 Rust 提交中击败了 100.00% 的用户
内存消耗 : 2 MB , 在所有 Rust 提交中击败了 100.00% 的用户
可以看到执行效率很高，几乎为0ms，循环的次数和数字的长度是一样的，算法复杂度是$O(n)$。其实这样又是从外到内的，同样可以使用递归来解决。
2019-09-25 07:40