738. Monotone Increasing Digits

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

1
2
3
4
5
6
7
8
9
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,找到第一个递减的数字。
记录最后一个连续相等的数字和下标记为v,直至第一个递减数字。例如12334551,我们只需要记录第一个5及其下标即可。
将v以后的所有数替换为0,再减一,加上递减之前的数字即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func monotoneIncreasingDigits(_ N: Int) -> Int {
let s = "\(N)"
var ans = 0
var v = (-1, -1)
var flag = false
for (i, char) in s.enumerated() {
guard i + 1 < s.count else {
break
}
let n = Int(String(char))!
let next = Int(String(s[s.index(s.startIndex, offsetBy: i + 1)]))!
if n > next {
flag = true
if v.0 == -1 || v.1 < n{
v = (i, n)
}
break
}else if n == next && v.1 != n{
v = (i, n)
}
ans = ans * 10 + n
}
guard flag else {
return N
}
var digit = 1
let power = s.count - v.0 - 1
//由于leetcode使用pow函数报错,借以此代替幂操作
for _ in 0..<power { digit *= 10 }
return v.1 * digit - 1 + N / digit / 10 * digit * 10
}
0%