单调递增的数字 | LeetCode-738 | 贪心算法

贪心练习题

---

LeetCode链接：738. 单调递增的数字

---

1.题目描述

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

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

示例 1:

输入: n = 10
输出: 9

示例 2:

输入: n = 1234
输出: 1234

示例 3:

输入: n = 332
输出: 299

提示:

• $0 <= n <= 10^9$

2.题解

2.1 贪心算法

• 思路：
  • 将输入整数 n 转换为字符串形式，并转换为字符数组，便于逐个字符操作。
  • 从数组的右侧开始遍历，检查是否存在前一位数字大于后一位数字的情况，如果存在，将前一位数字减 1 并记录从哪里开始需要将数字置为 9。
  • 在从 start 标记位置开始，将所有后续数字替换为 9 以保证结果是单调递增的。
  • 最后将修改后的字符数组转换回整数并返回。

class Solution {
    public int monotoneIncreasingDigits(int n) {
        // 将输入数字转换为字符串形式
        String s = String.valueOf(n);
        // 将字符串转换为字符数组，方便操作每个数字
        char[] chs = s.toCharArray();
        // 初始化 start 变量，标记从哪个位置开始需要将字符置为 '9'
        int start = chs.length;
        
        // 从字符数组的倒数第二位开始遍历，向前检查
        for(int i = chs.length - 1; i > 0; i--) {
            // 如果前一个字符比当前字符大
            if(chs[i - 1] > chs[i]) {
                // 将前一个字符减 1
                chs[i - 1]--;
                // 更新 start，标记需要置为 '9' 的起始位置
                start = i;
            }
        }
        
        // 将 start 位置及其之后的所有字符置为 '9'
        for(int i = start; i < chs.length; i++) {
            chs[i] = '9';
        }
        return Integer.parseInt(String.valueOf(chs));
    }
}