题目描述
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
示例 1:
示例 2:
示例 3:
提示:
解法一：贪心
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
32
33
34
|
func monotoneIncreasingDigits(n int) int {
numStr := []byte(strconv.Itoa(n))
i, j := 0, 1
for j < len(numStr) {
if numStr[j] >= numStr[i] {
i++
j++
} else {
// numStr[j] < numStr[i]
break
}
}
if j == len(numStr) {
return n
} else {
for j < len(numStr) {
numStr[j] = '9'
j++
}
numStr[i] -= 1
j = i
i--
for i >= 0 && numStr[i] > numStr[j] {
numStr[j] = '9'
numStr[i] -= 1
i--
j--
}
}
res, _ := strconv.Atoi(string(numStr))
return res
}
|
官方题解如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
func monotoneIncreasingDigits(n int) int {
s := []byte(strconv.Itoa(n))
i := 1
for i < len(s) && s[i] >= s[i-1] {
i++
}
if i < len(s) {
for i > 0 && s[i] < s[i-1] {
s[i-1]--
i--
}
for i++; i < len(s); i++ {
s[i] = '9'
}
}
ans, _ := strconv.Atoi(string(s))
return ans
}
|
思考：和官方题解比较后发现我的代码中同时使用了两个变量 j 和 i，其实只需要一个就可以了。
