当前位置：首页 > news >正文

算法训练营Day33

news 2025/8/23 18:16:12

#Java #贪心

开源学习资料

Feeling and experiences：

单调递增的数字：力扣题目链接

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

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

示例 1:

输入: n = 10
输出: 9

该题我首先想到的是暴力解法，判断这个n是否是满足要求递增的，如果不满足就n--：

class Solution {public int monotoneIncreasingDigits(int n) {while(n>=0){if(!isIncrease(n)){n--;}else{return n;}}return n;}public boolean isIncrease(int n){while(n>0){int n1 = n%10;int n2 = (n/10)%10;n/=10;if(n1 < n2){return false;}}return true;}
}

这样超过了时间限制，而且一看效率就很低了。

正确的做法：

class Solution {public int monotoneIncreasingDigits(int n) {char[] digits = String.valueOf(n).toCharArray();int mark = digits.length;for (int i = digits.length - 1; i > 0; i--) {if (digits[i] < digits[i - 1]) {mark = i;digits[i - 1]--;}}for (int i = mark; i < digits.length; i++) {digits[i] = '9';}return Integer.parseInt(new String(digits));
}}

1. 将数字转换为字符数组：首先，将输入的整数 n 转换为字符数组，以便逐位处理。

2. 从右向左遍历：从最低位开始向最高位遍历。这样做的目的是找到第一个违反单调递增规则的点。即找到第一个 digits[i] < digits[i - 1] 的位置。

3. 标记并调整数字：一旦找到这样的点（即 digits[i] < digits[i - 1]），执行两个操作：
• 将 digits[i - 1] 减一（因为要保持整体数字的大小尽可能大，但又要小于原来的 N）。
• 记录当前位置 i，这是因为从这一位开始到最低位的所有数字都需要被设置为 9（以保证这部分是最大的单调递增数字）。

4. 将标记后面的数字全部变成9：从标记的位置开始，将所有更低位的数字替换为 9。这是因为我们已经减少了前面的一位数字，所以可以安全地将这些位设置为最大可能值（9）以得到最大的单调递增数字。

5. 转换回整数并返回：最后，将修改后的字符数组转换回整数，并返回这个整数。