leetcode 738. Monotone Increasing Digits 最大单调递增数字 + 找规律

青旅半醒 2022-06-03 09:45 160阅读 0赞

Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits.

(Recall that an integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.)

Example 1:  
Input: N = 10  
Output: 9  
Example 2:  
Input: N = 1234  
Output: 1234  
Example 3:  
Input: N = 332  
Output: 299  
Note: N is an integer in the range \[0, 10^9\].

本题题意很简单，就是求小于等于N的一个最大的数字，该数每一位是单调递增的。

那么我们就来分析题目中给的几个例子吧，首先如果是10的话，我们知道1大于0，所以不是单调自增的，那么返回的数就是9。第二个例子是1234，各位上已经满足单调自增的条件了，返回原数即可。第三个例子是332，我们发现最后一位2小于之前的3，那么此时我们将前面位减1，先变成322，再往前看，还是小于前面的3，那么我们再将前面位减1，就变成了222，此时222不是最大的单调递增数，我们可以将后面两位变成9，于是乎就有了299，小于给定的332，符合题意。如果给定的数字是232，那么就会得到229，我们可以发现规律，要找到从后往前遍历的最后一个值升高的位置，让前一位减1，并把当前位以及后面的所有位都变成9，就可以得到最大的单调递增数啦。

我们用j表示最后一个值升高的位置，具体来说应该是其前一位的值大，初始化为总位数n，然后从后往前遍历，因为每次要和前一位比较，为防止越界，应遍历到第二个数停止，如果当前位大于等于前一位，符合单调递增，直接跳过；否则就将前一位自减1，j赋值为当前位i，循环结束后，从j位到末尾的位数都改为9即可，

建议和[leetcode 402. Remove K Digits 贪心算法 + DFS深度优先遍历][leetcode 402. Remove K Digits _ _ DFS] 和[leetcode 321. Create Maximum Number 根据两个整数创造一个有k位的最大的数 + 贪心算法][leetcode 321. Create Maximum Number _k_ _]一起学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        int monotoneIncreasingDigits(int n)
        {
            string num = to_string(n);
            int begin = num.length();
            for (int i = num.length() - 1; i >= 1; i--)
            {
                if (num[i] >= num[i - 1])
                    continue;
                else
                {
                    num[i - 1]--;
                    begin = i;
                }
            }
            for (int i = begin; i < num.length(); i++)
                num[i] = '9';
            return stoi(num);
        }
    };

[leetcode 402. Remove K Digits _ _ DFS]: http://blog.csdn.net/jackzhang_123/article/details/78743050
[leetcode 321. Create Maximum Number _k_ _]: http://blog.csdn.net/jackzhang_123/article/details/78150508