题目描述：

LeetCode 738. Monotone Increasing Digits

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].

题目大意：

给定整数N，求不大于N的最大整数，其各位数单调不减。

解题思路：

从高位向低位遍历整数N的各位数，找到第一个违反单调不减的数的下标x

将x位后的所有数替换为0，记得到的新数为M，则M - 1即为答案

Python代码：

class Solution(object):
    def monotoneIncreasingDigits(self, N):
        """
        :type N: int
        :rtype: int
        """
        sn = str(N)
        size = len(sn)
        flag = False
        for x in range(size - 1):
            if sn[x] > sn[x + 1]:
                flag = True
                break
        if not flag: return N
        while x > 0 and sn[x - 1] == sn[x]: x -= 1
        y = len(sn) - x - 1
        return (N / (10 ** y)) * (10 ** y) - 1

 

本文链接：http://bookshadow.com/weblog/2017/12/03/leetcode-monotone-increasing-digits/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码