LC 738.单调递增的数字

本文主要是介绍LC 738.单调递增的数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

738.单调递增的数字

当且仅当每个相邻位数上的数字 x 和 y 满足 $x\le y$ 时，我们称这个整数是单调递增的。

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

示例 1:

输入: n = 10
输出: 9

示例 2:

输入: n = 1234
输出: 1234

示例 3:

输入: n = 332
输出: 299

提示:

• $0\le n\le 109$

解法一(贪心)

思路分析：

1. 即对于整数n，即当某一位小于前一位时，则将前一位减一，从当前位到开始，后序位均设为9
2. 因此先将整数n转化为整型数组，从前往后遍历，当当前位上的数小于前一位上的数字时，再将后续位均设为9
3. 但是此时考虑特殊情况，555554，若按照上述逻辑执行，则会出现得到值位555549的情况，不满足题意
4. 所以在上述逻辑，再套一层循环，只需检查$lo{g}^n$次，查看是否已经实现单调递增，即可

实现代码如下：

class Solution {public int monotoneIncreasingDigits(int n) {if (n == 0) return n;String str = String.valueOf(n);	// 将其转化为字符串int len = str.length();	// 获取整数n的位数int[] nums = new int[len];	// 存储n的对应位上的值for (int i = 0; i < len; ++ i) {	// 字符串转化为整型数组nums[i] = str.charAt(i) - '0';}for (int i = 0; i < len; ++ i) {boolean flag = true;	// 判断当前的整数数组 是否单调递增for (int j = 1; j < len; ++ j) {if (nums[j] < nums[j-1]) {	// 若当前位小于上一位nums[j-1] -= 1;	// 上一位减一while (j < len) {	// 后续位 全部变成9nums[j] = 9;++ j;}flag = false;	// 表示不单调递增break;}}if (flag) break;}int ans = 0;	// 将已经确定的递增数组 转化为整数for (int i = 0; i < len; ++ i) {ans = ans*10 + nums[i];}return ans;}
}

提交结果如下：

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.6 MB,击败了65.04% 的Java用户

复杂度分析：

• 时间复杂度：$O(lo{g}^n\times lo{g}^n)$
• 空间复杂度：$O(lo{g}^n)$

解法二(优化解法一)

思路分析：

1. 在解法一提到的逻辑问题；可以转换思路来避免
2. 即将整数n转化为数组后，从后往前遍历，当遍历到某位上的数值，大于前一位时，说明需要前一位减一，并将当前位及后的数值改为9
3. 如此，则不会出现555554得到555549的情况，因为是从后往前遍历，在遍历过程中已经隐形检查了一边数组，保证为单调递增

实现代码如下：

class Solution {public int monotoneIncreasingDigits(int n) {if (n == 0) return n;String str = String.valueOf(n);	// 将其转化为字符串int len = str.length();	// 获取整数n的位数int[] nums = new int[len];	// 存储n的对应位上的值for (int i = 0; i < len; ++ i) {	// 字符串转化为整型数组nums[i] = str.charAt(i) - '0';}for (int i = len-1; i > 0; --i) {	// 从后往前遍历数组if (nums[i] < nums[i-1]) {	// 若当前位小于前一位nums[i-1] -= 1;	// 前一位减一for (int j = i; j < len; ++ j)nums[j] = 9;}}int ans = 0;	// 将已经确定的递增数组 转化为整数for (int i = 0; i < len; ++ i) {ans = ans*10 + nums[i];}return ans;}
}

提交结果如下：

解答成功:
执行耗时:0 ms,击败了100.00% 的Java用户
内存消耗:39.7 MB,击败了31.42% 的Java用户

复杂度分析：

• 时间复杂度：$O(lo{g}^n)$
• 空间复杂度：$O(lo{g}^n)$

这篇关于LC 738.单调递增的数字的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---