738. 单调递增的数字

问题描述

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

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

示例 1:

输入: N = 10
输出: 9

示例 2:

输入: N = 1234
输出: 1234

示例 3:

输入: N = 332
输出: 299

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

解题思路

假设 \(N\) 的从高位到低位的数字依次为 \(a_0,\cdots,a_{n-1}\)，从高位 \(a_0\) 往低位 \(a_{n-1}\) 遍历。

第一次遇到 \(a_i\lt a_{i-1}\) 时结束。

此时令 \(s[i-1]=s[i-1]-1\)，然后判断 \(s[i-1]\) 与 \(s[i-2]\) 的大小是否满足条件，一直重复往前判断直到满足 \(s[j-1]\le s[j]\)，然后将 \(s[j+1:n]\) 全部变为 \(9\) 即可。

---

class Solution:
    def monotoneIncreasingDigits(self, N: int) -> int:
        s = list(map(int, str(N)))
        n = len(s)
        for i in range(1, n):
            if s[i] < s[i - 1]:
                j = i
                while j >= 1 and s[j] < s[j - 1]:
                    s[j - 1] -= 1
                    j -= 1
                s[j + 1 :] = [9] * (n - j - 1)
                break
        return int("".join(map(str, s)))

返回顶部

在手机上阅读