单调递增的数字Java
文章发布较早,内容可能过时,阅读注意甄别。
# 题目
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。
给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增 。
示例 1:
输入: n = 10
输出: 9
示例 2:
输入: n = 1234
输出: 1234
示例 3:
输入: n = 332
输出: 299
提示:
- 0 <= n <= 109
# 思路
/**
* 思路:
* 从右向左扫描数字,若发现当前数字比其左边一位(较高位)小,
* 则把其左边一位数字减1,并将该位及其右边的所有位改成9
*/
# 解法
class Solution {
/**
* 思路:
* 从右向左扫描数字,若发现当前数字比其左边一位(较高位)小,
* 则把其左边一位数字减1,并将该位及其右边的所有位改成9
*/
public int monotoneIncreasingDigits(int n) {
String s = String.valueOf(n);
int length = s.length();
char[] chars = s.toCharArray();
int flag = length;
for (int i = length - 1; i >= 1; i--) {
if (chars[i] < chars[i - 1]) {
flag = i;
chars[i - 1]--;
}
}
for (int i = flag; i < length; i++) {
chars[i] = '9';
}
return Integer.parseInt(new String(chars));
}
}
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
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
# 总结
- 分析出几种情况,然后分别对各个情况实现