Medium

题目描述

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

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

示例 1：

输入：n = 10
输出：9

示例 2：

输入：n = 1234
输出：1234

示例 3：

输入：n = 332
输出：299

约束条件：

  • 0 ≤ n ≤ 10^9

提示：

  • 逐位构建答案，添加可能的最大数字，使得数字仍然小于或等于 N。

解题思路

解题思路

这道题要求找到小于等于 n 的最大单调递增数字。核心思想是贪心算法。

方法分析

贪心策略： 从右向左扫描数字，如果发现某一位比前一位小（违反单调递增），就需要调整：

  1. 将前一位减1
  2. 将当前位及后面所有位都设为9

为什么从右向左？ 因为我们要保证结果尽可能大，所以优先处理低位的调整。从右向左可以确保每次调整都是最优的。

具体步骤：

  1. 将数字转换为字符数组便于操作
  2. 从右向左遍历，找到第一个违反单调递增的位置
  3. 将该位置的前一位减1，后面所有位设为9
  4. 继续向左检查，确保调整后仍满足单调递增

示例分析：

  • n = 332：发现3 > 2，将第一个3减1变成2，后面设为9，得到299
  • n = 1234：本身就是单调递增，直接返回1234
  • n = 10：发现1 > 0，将1减1变成0，但0开头无意义，所以结果是9

时间复杂度O(log n)，空间复杂度O(log n)。

代码实现

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string s = to_string(n);
        int flag = s.size(); // 标记从哪一位开始变为9
        
        for (int i = s.size() - 2; i >= 0; i--) {
            if (s[i] > s[i + 1]) {
                flag = i + 1;
                s[i]--;
            }
        }
        
        for (int i = flag; i < s.size(); i++) {
            s[i] = '9';
        }
        
        return stoi(s);
    }
};

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        s = list(str(n))
        flag = len(s)  # 标记从哪一位开始变为9
        
        for i in range(len(s) - 2, -1, -1):
            if s[i] > s[i + 1]:
                flag = i + 1
                s[i] = str(int(s[i]) - 1)
        
        for i in range(flag, len(s)):
            s[i] = '9'
        
        return int(''.join(s))

public class Solution {
    public int MonotoneIncreasingDigits(int n) {
        char[] s = n.ToString().ToCharArray();
        int flag = s.Length; // 标记从哪一位开始变为9
        
        for (int i = s.Length - 2; i >= 0; i--) {
            if (s[i] > s[i + 1]) {
                flag = i + 1;
                s[i]--;
            }
        }
        
        for (int i = flag; i < s.Length; i++) {
            s[i] = '9';
        }
        
        return int.Parse(new string(s));
    }
}

var monotoneIncreasingDigits = function(n) {
    let s = n.toString().split('');
    let flag = s.length; // 标记从哪一位开始变为9
    
    for (let i = s.length - 2; i >= 0; i--) {
        if (s[i] > s[i + 1]) {
            flag = i + 1;
            s[i] = String.fromCharCode(s[i].charCodeAt(0) - 1);
        }
    }
    
    for (let i = flag; i < s.length; i++) {
        s[i] = '9';
    }
    
    return parseInt(s.join(''));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log n)需要遍历数字的每一位，位数为 log n
空间复杂度O(log n)需要存储数字字符串，长度为 log n

相关题目