题目分析

这是一个数学题，数学题的做法是找到规律，往往可以用贪心的思路进行解题。

贪心

要求是满足每一位都是单调递增的。那么如果出现递减应该如何修改呢？

如果出现递减，我们就要将前一位减1，然后将后面的所有位都置为9，这样才能满足小于等于N，且结果最大，这就是本题的贪心思想。

但是小伙伴们要注意向前面借一位，可能会导致前面的位数不是单调递减的。如332这个例子，我们发现第二个3后面有一个2，因此2会向3借一位，因此第二个3变成了2，然后在后面所有位置9，变为329。但是这就会导致新产生的2和前面的3不满足单调递增关系，因此要再次操作，最多会操作9次。

因为我们按照位来操作，因此算法的**时间复杂度为$O(log^2(n))$，空间复杂度为$O(log(n))$**。

#include<iostream>
#include<vector>
#include<string>

using namespace std;

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string strN = to_string(N);
        while (1) {
            for (int i = 1; i < strN.size(); i++) {
                if (strN[i - 1] > strN[i]) {
                    strN[i - 1] -= 1;
                    for (int j = i; j < strN.size(); j++) {
                        strN[j] = '9';
                    }
                    break;
                }
                if (i == strN.size() - 1) { return stoi(strN); }
            }
        }
        return stoi(strN);
    }
};

优化贪心

我们发现上面做法虽然很快，但是仍然有很多冗余操作，因为对于后面置9的操作可能会做很多次。

举一个例子，33332，第一次遍历后会变成33329，此时最后一位置9，第二次遍历后会变成33299，此时最后两位置9，第三次遍历后会变成32999，此时最后三位置9，第四次遍历后会变成29999，此时最后4位置9。最后一位置了4次9，每一次遍历都会重新赋值一次。因为题目中的整数是位于[0, 1e9]，所以$log^2(1e9)$也非常小，因此感觉速度非常快。

我们还可以对其优化，如果我们用right表示末尾置9的位置，如上例，第一次将最后一位置9后，第二次遍历我们就将倒数第二位置9即可，这样最多置log(n)个9。

算法的**时间复杂度为$O(log(n))$，空间复杂度为$O(log(n))$**。

#include<iostream>
#include<vector>
#include<string>

using namespace std;

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string strN = to_string(N);
        int right = strN.size();
        while (right > 1) {
            for (int i = 1; i < right; i++) {
                if (strN[i - 1] > strN[i]) {
                    strN[i - 1]--;
                    for (int j = i; j < right; j++) {
                        strN[j] = '9';
                    }
                    right = i;
                    break;
                }
                if (i == right - 1) { return stoi(strN); }
            }
        }
        return stoi(strN);
    }
};

双指针

这个题目还可以进行优化，我们仍然举33332的例子说明，每次修改时，只可能影响到前一位，如第一次遍历后会变成33329，此时只可能影响到第三个3，对前两个3不会产生影响。我们在第二次遍历时，直接从2开始和前面的3比较即可，不用从第一位开始。同理第二次遍历后会变成33299，此时只可能影响到第二个3，对第一个3也不会产生影响。

我们再用left表示从哪一位开始比较，又可以对其进行优化。算法的**时间复杂度为$O(log(n))$，空间复杂度为$O(log(n))$**。

#include<iostream>
#include<vector>
#include<string>

using namespace std;

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string strN = to_string(N);
        int left = 1, right = strN.size();
        while (left < right) {
            for (int i = left; i < right; i++) {
                if (strN[i - 1] > strN[i]) {
                    left = i > 1 ? i - 1 : 1;
                    strN[i - 1]--;
                    for (int j = i; j < right; j++) {
                        strN[j] = '9';
                    }
                    right = i;
                    break;
                }
                if (i == right - 1) { return stoi(strN); }
            }
        }
        return stoi(strN);
    }
};

刷题总结

数学问题有时候比较绕人，思路不清晰会被绕进去，不过数学问题一般都是按位进行操作，方法正确不会出现超时。这个题目在笔试面试时只要找准贪心的核心思想，即使没有想到双指针的思路，用普通的方法也是可以的。