单调递增的数字
# 📃 题目描述
题目链接:738. 单调递增的数字 - 力扣(LeetCode) (leetcode-cn.com) (opens new window)
给定一个非负整数 N,找出小于或等于 N 的最大的整数,同时这个整数需要满足其各个位数上的数字是单调递增。
(当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。)
示例 1:
输入: N = 10
输出: 9
示例 2:
输入: N = 1234
输出: 1234
示例 3:
输入: N = 332
输出: 299
# 🔔 解题思路
和 31. 下一个排列 - 力扣(LeetCode) (leetcode-cn.com) (opens new window) 有点像,不过这题好像更简单点
# 暴力解法
暴力解法,将 N 不断缩小,每减小一个就判断一次是否数字是递增排序的,如果是,则直接返回
class Solution {
public int monotoneIncreasingDigits(int n) {
for (int i = n; i >= 0; i --) {
if (checkNum(i)) {
return i;
}
}
return 0;
}
// 判断数字 i 的每位是否是递增的
private boolean checkNum(int i) {
int maxNum = 10;
while (i != 0) {
int temp = i % 10;
if (temp <= maxNum) {
maxNum = temp;
i /= 10;
}
else {
return false;
}
}
return true;
}
}
时间复杂度 O(N * M),M 是数字 N 的长度,LeetCode 上提交会超时
# 贪心算法
题目需要找出小于或等于 n 的最大的整数,同时这个整数需要满足其各个位数上的数字是单调递增。
也就是说,如果这个 n 的各个位已经是单调递增的了(前一位小于后一位),那么就要不进行任何改变
换句话说,我们要考虑的其实就是前一位比后一位大的情况:
- 局部最优:遇到 n[i - 1] > n[i]的情况,让 n[i - 1]--,然后 n[i] 直接赋值为 9,可以保证这两位变成最大单调递增整数。
- 全局最优:得到小于等于 n 的最大单调递增的整数
从前后向遍历会改变已经处理的结果,所以我们需要从后往前遍历
举个例子:
322 -> 322 -> 292
可以看到,有可能出现前一个数和后一个数相同的情况,这种情况下是符合题意的,但是如果我们不进行处理,就会出现这个例子的情况。这里最后的 2 也应该变成 9
所以我们需要一个标志位 flag,来表示 flag 及之后的数都需要变为 9,比如这个例子中的 flag 就是 1,表示下标 1 以及其之后的数,都得变成 9.
class Solution {
public int monotoneIncreasingDigits(int n) {
char[] chars = Integer.toString(n).toCharArray();
// flag 及之后的数都需要变为 9
int flag = chars.length;
for (int i = chars.length - 1; i > 0; i --) {
if (chars[i - 1] > chars[i]) {
chars[i - 1] -= 1;
flag = i;
}
}
if (flag == arr.length) {
return n;
}
for (; flag < chars.length; flag ++) {
chars[flag] = '9';
}
// 处理 09xxx 的情况,去掉开头的 0
if (chars[0] == '0' && chars.length > 1) {
char[] res = new char[chars.length - 1];
int index = 0;
for (int i = 1; i < chars.length; i ++) {
res[index ++] = chars[i];
}
return Integer.parseInt(String.valueOf(res));
}
return Integer.parseInt(String.valueOf(chars));
}
}
- 空间复杂度:O(N)
- 时间复杂度:O(N)
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~