原文链接: https://leetcode-cn.com/problems/monotone-increasing-digits

英文原文

An integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.

Given an integer n, return the largest number that is less than or equal to n with monotone increasing digits.

 

Example 1:

Input: n = 10
Output: 9

Example 2:

Input: n = 1234
Output: 1234

Example 3:

Input: n = 332
Output: 299

 

Constraints:

• 0 <= n <= 109

中文题目

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

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

示例 1:

输入: N = 10
输出: 9

示例 2:

输入: N = 1234
输出: 1234

示例 3:

输入: N = 332
输出: 299

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

通过代码

高赞题解

分析

由于结果要求各位数字单调递增，那么这些数字必然形如 a0a1a2……an (1 <= a0 <= a1 <= a2 <= …… <= an <= 9)

显然有：

      --------------
      a0 a1 a2 …… an      (1 <= a0 <= a1 <= a2 <= …… <= an <= 9)

=     a0 *  111……1    + (a1 - a0) *   111……1    
           \-n个1-/                 \-(n-1)个1-/ 

   + (a2 - a1) *   111……1    + ………… + (an - an-1) * 1
                 \-(n-2)个1-/

可见最终结果必然是若干个形如 11……11 的数字相加所得。

本题中，最大的n为10^9，所以，可以从111111111开始依次累加，如果继续累加将导致结果超过n，则去掉一个1继续循环。总累加次数不超过9次。

代码

[]
impl Solution {
    pub fn monotone_increasing_digits(n: i32) -> i32 {
        let mut ones = 111111111;
        let mut result = 0;
        for _ in 0..9 {
            while result + ones > n {
                ones /= 10;
            }
            result += ones;
        }
        result
    }
}

[]
class Solution:
    def monotoneIncreasingDigits(self, N: int) -> int:
        ones = 111111111
        result = 0
        for _ in range(9):
            while result + ones > N:
                ones //= 10
            result += ones
        return result

统计信息

通过次数	提交次数	AC比率
43690	87159	50.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
移掉 K 位数字	中等