跳转至

738. 单调递增的数字

难度中等

题目描述

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

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

 

示例 1:

输入: n = 10
输出: 9

示例 2:

输入: n = 1234
输出: 1234

示例 3:

输入: n = 332
输出: 299

 

提示:

  • 0 <= n <= 109

解法

方法一：贪心

思考

求不超过 \(n\) 的最大各位非降数。从 \(n\) 向下逐个检查位数过多；需要直接改数字本身。

从高位找到第一处下降后，若只把后面改成 \(9\)，前面可能仍大于原数。应把下降处左侧连续偏大的位都减一，直到重新非降，再把右侧全部置 \(9\)，得到的是不超过 \(n\) 的最大非降数。

先扫到第一处 \(s[i-1]>s[i]\)，再回退减一，最后把 \(i\) 之后写成 \(9\)。位数为 \(O(\log n)\)。

从数字 n 的高位开始，找到第一个不满足 \(n_{i-1} \le n_i\) 的位置 \(i\)。

然后，从后往前，只要发现 \(n_{i-1} \gt n_i\)，就将 \(n_{i-1}\) 减 1。

最后将位置 \(i\) 之后的所有数字都置为 9 即可。

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        s = list(str(n))
        i = 1
        while i < len(s) and s[i - 1] <= s[i]:
            i += 1
        if i < len(s):
            while i and s[i - 1] > s[i]:
                s[i - 1] = str(int(s[i - 1]) - 1)
                i -= 1
            i += 1
            while i < len(s):
                s[i] = '9'
                i += 1
        return int(''.join(s))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int monotoneIncreasingDigits(int n) {
        char[] s = String.valueOf(n).toCharArray();
        int i = 1;
        for (; i < s.length && s[i - 1] <= s[i]; ++i)
            ;
        if (i < s.length) {
            for (; i > 0 && s[i - 1] > s[i]; --i) {
                --s[i - 1];
            }
            ++i;
            for (; i < s.length; ++i) {
                s[i] = '9';
            }
        }
        return Integer.parseInt(String.valueOf(s));
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string s = to_string(n);
        int i = 1;
        for (; i < s.size() && s[i - 1] <= s[i]; ++i)
            ;
        if (i < s.size()) {
            for (; i > 0 && s[i - 1] > s[i]; --i) {
                --s[i - 1];
            }
            ++i;
            for (; i < s.size(); ++i) {
                s[i] = '9';
            }
        }
        return stoi(s);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func monotoneIncreasingDigits(n int) int {
    s := []byte(strconv.Itoa(n))
    i := 1
    for ; i < len(s) && s[i-1] <= s[i]; i++ {
    }
    if i < len(s) {
        for ; i > 0 && s[i-1] > s[i]; i-- {
            s[i-1]--
        }
        i++
        for ; i < len(s); i++ {
            s[i] = '9'
        }
    }
    ans, _ := strconv.Atoi(string(s))
    return ans
}

评论