Monotone Increasing Digits

738. 单调递增的数字

分析

将 n 转换为字符串 s
找到 第一个下降的位置，即前一位大于后一位
为了让整体数值最大:
- 将下降点前一个位置的数减 1
  - 注意：如果前面有连续相同的数字，需要往前找到第一个不同的数字再减 1
- 后面的所有位数填成 '9'

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution
{
public:
    int monotoneIncreasingDigits(int n)
    {
        std::string s = std::to_string(n);
        int k = 0;

        // 先找到第一个下降的位置
        while (k + 1 < s.size() && s[k] <= s[k + 1])
            ++ k;

        // 如果本身已经是单调递增，直接返回 n
        if (k == s.size() - 1)
            return n;

        // 否则，需要回退到第一个不同的位置
        while (k && s[k] == s[k - 1])
            -- k;

        // 将第 k 位减 1
        s[k] -= 1;

        // 将 k+1 及之后的位置全部置为 '9'
        for (int i = k + 1; i < s.size(); ++ i)
            s[i] = '9';

        return std::stoi(s);
    }
};