算法题：单调递增的数字

描述

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

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

示例 1:

输入: N = 10
输出: 9
示例 2:

输入: N = 1234
输出: 1234
示例 3:

输入: N = 332
输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。

链接：https://leetcode-cn.com/problems/monotone-increasing-digits

思路

要想结果最大，应该尽量与N的高位对齐，从第一个无法对齐的开始，所有位都置为9。
具体操作：从高位开始依次遍历N的每一位，若第i位小于i-1位，则第i-1位减一，由于有可能之前i-2等于i-1，则还需从i-1往前走，每次减一之后与前一位比较，直到前一位仍然小于等于当前位。从当前位开始，所有低位置为9.

代码

C++

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        vector<int> M;
        while (N > 0) {
            M.push_back(N % 10);
            N /= 10;
        }
        reverse(M.begin(), M.end());
        
        for (int i = 1;i < M.size();i++) {
            if (M[i] < M[i-1]) {
                int j = i;
                for (;j > 0;j--) {
                    if (M[j] < M[j-1])
                        M[j-1] = M[j-1]-1;
                    else break;
                }
                j++;
                for (;j < M.size();j++) {
                    M[j] = 9;
                }
                break;
            }
        }

        int res = 0;
        for (int i = 0;i < M.size();i++) {
            res  = res * 10 + M[i];
        }
        return res;
    }
};

复杂度
时间复杂度：O(n)，n为N的位数
空间复杂度：O(n)