0738. 单调递增的数字【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 贪心

1. 📝 题目描述

• leetcode

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

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

---

示例 1：

输入: n = 10
输出: 9

示例 2：

输入: n = 1234
输出: 1234

示例 3：

输入: n = 332
输出: 299

---

提示：

• 0 <= n <= 10^9

2. 🎯 s.1 - 贪心

c

int monotoneIncreasingDigits(int n) {
    char s[12];
    sprintf(s, "%d", n);
    int len = strlen(s), mark = len;
    for (int i = len - 1; i > 0; i--) {
        if (s[i] < s[i - 1]) {
            mark = i;
            s[i - 1]--;
        }
    }
    for (int i = mark; i < len; i++) s[i] = '9';
    return atoi(s);
}

js

/**
 * @param {number} n
 * @return {number}
 */
var monotoneIncreasingDigits = function (n) {
  const digits = ('' + n).split('')
  let mark = digits.length
  for (let i = digits.length - 1; i > 0; i--) {
    if (digits[i] < digits[i - 1]) {
      mark = i
      digits[i - 1] = '' + (+digits[i - 1] - 1)
    }
  }
  for (let i = mark; i < digits.length; i++) digits[i] = '9'
  return +digits.join('')
}

py

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        digits = list(str(n))
        mark = len(digits)
        for i in range(len(digits) - 1, 0, -1):
            if digits[i] < digits[i - 1]:
                mark = i
                digits[i - 1] = str(int(digits[i - 1]) - 1)
        for i in range(mark, len(digits)):
            digits[i] = '9'
        return int(''.join(digits))

• 时间复杂度：$O(d)$，其中 d 是数字位数
• 空间复杂度：$O(d)$

算法思路：

• 从右向左扫描，若出现逆序（digits[i] < digits[i-1]），将 digits[i-1] 减 1 并记录位置
• 从记录位置开始将后续所有位置置为 9