题目地址：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 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发