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%