题目地址:https://leetcode.com/problems/monotone-increasing-digits/description/

题目描述:

Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits.

(Recall that an integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.)

Example 1:

Input: N = 10
Output: 9

Example 2:

Input: N = 1234
Output: 1234

Example 3:

Input: N = 332
Output: 299

Note: N is an integer in the range [0, 10^9].

题目大意

找出一个比这个数字小的,每位数字都是递增的最大数字。

解题方法

把题目给出的数字拆分成数组进行理解。如果这么理解之后,那我们就是要找到一个最大的递增数组。

做的方法是找出第一个降序的位置,有两种情况:

case 1: 对于 14267 , 第一个出现下降的位置是4,所以把4变成3,把4后面的数字全部改成9.得到13999;

case 2: 对于1444267, 第一个降序的位置是最后一个4,如果只把最后一个4按照case1处理,那么得到的是1443999,仍然不满足题意。所以需要找到第一个位置的4,然后做case1操作,这样得到的是1399999。

写代码的时候我是逆序过来做的,然后我犯了一个错误,写成了num[i] > num[i - 1] or (ind != -1 and num[i] == num[i - 1])。为什么不能是num[i] == num[i - 1]呢?因为这样会找到最后的一个相等的位置,而我们只需要找到最先出现相等的位置即可。

时间复杂度是O(n),空间复杂度是O(n).

代码如下:

class Solution:
    def monotoneIncreasingDigits(self, N):
        """
        :type N: int
        :rtype: int
        """
        if N < 10: return N
        num = [int(n) for n in str(N)[::-1]]
        n = len(num)
        ind = -1
        for i in range(1, n):
            if num[i] > num[i - 1] or (ind != -1 and num[i] == num[ind]):
                ind = i
        if ind == -1:
            return N
        res = '9' * ind + str(num[ind] - 1) + "".join(map(str, num[ind + 1:]))
        return int(res[::-1])

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

如果不使用逆序,也可以做:

class Solution:
    def monotoneIncreasingDigits(self, N):
        """
        :type N: int
        :rtype: int
        """
        if N < 10: return N
        num = [int(n) for n in str(N)]
        n = len(num)
        ind = n - 1
        for i in range(n - 2, -1, -1):
            if num[i] > num[i + 1] or (ind != n - 1 and num[i] == num[ind]):
                ind = i
        if ind == n - 1:
            return N
        num[ind] -= 1
        for i in range(ind + 1, n):
            num[i] = 9
        return int("".join(map(str, num)))

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

参考资料:

https://leetcode.com/problems/monotone-increasing-digits/discuss/109794/Simple-Python-solution-w-Explanation

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发