Monotone Increasing Digits

发表于

「这是我参与11月更文挑战的第19天，活动详情查看：2021最后一次更文挑战」。

LeetCode题目链接

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.)
Note: N is an integer in the range [0, 10^9].

给一个非负整数N，找出最大的、不大于N的monotone increasing digits X。所谓monotone increasing digits 指的是从左往右看，每位数字都是单调非减，如12345， 12233。

X要满足两个条件，①X<=N且X要尽可能大 ②X的各位数字dandianfeijian。该怎么找这样的数字呢？从哲学的角度想，解铃还须系铃人，肯定要从N入手。

首先如果N本身就是monotone increasing digits ，那么X=N；如果N不是，那么就需要依据N构造出X。要满足条件①，从高位开始X的数字要和N的数字尽可能相等；当不能相等时（假设是第i位），也就是为了满足条件②，我们只能第i-1位数字减小，i-1后的数字变为9。

1
2
3
ini复制代码	以N=1234532为例：
	N = 1 2 3 4 5 3 2
	X  = 1 2 3 4 5 _ _

第i=6位时，X的第6位如果取3则不满足条件②，又不能取一个更大的数字，这样会违反条件①，这种情况下只能让第i-1=5位数字减一：

1
2
ini复制代码	N = 1 2 3 4 5 3 2
	X  = 1 2 3 4 4 _ _

此时X已经小于N，故后面的数字全取9也不会大于N，同时也满足条件②。
看起来这样已经解决这个问题了，其实我们忽略了一个地方，那就是第i-1位减一后，可能会出现Xi−2>Xi−1X_{i-2} \gt X_{i-1}Xi−2​>Xi−1​ 的情况，这样就违反了条件②。如：33321

1
2
ini复制代码	N = 3 3 3 2 1
	X = 3 3 2 9 9（之前做法得到的结果）

所以我们还需要向前检查，当发生Xi−1>XiX_{i-1} \gt X_{i}Xi−1​>Xi​ 的情况时，Xi−1X_{i-1}Xi−1​ -= 1， 继续向前检查，直到满足Xi−1≤XiX_{i-1} \le X_{i}Xi−1​≤Xi​ ， 然后从i开始所有的数字取9。

1
2
ini复制代码	N = 3 3 3 2 1
	X = 2 9 9 9 9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ini复制代码class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string str = to_string(N);
        int len = str.size();
        if (len == 1) return N;
        for (int i = 1;i < len;++i){
            if (str[i] < str[i-1]){//找到违反单调不减的下标
                int t = i;
                while (t>=1 && str[t-1]>str[t]){//向前检查
                    --str[t-1];
                    --t;
                }
                for (int k =t+1;k < len;++k)//t之后的数字取9
                    str[k] = '9';
                break;
            }
        }
        cout << str << endl;
        return atoi(str.c_str());
    }
};

看到还有人的做法如下：

解题思路：从高位向低位遍历整数N的各位数，找到第一个违反单调不减的数的下标x将x及x后的所有数替换为0，记得到的新数为M，则M - 1即为答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
python复制代码class Solution(object):
    def monotoneIncreasingDigits(self, N):
        """
        :type N: int
        :rtype: int
        """
        sn = str(N)
        size = len(sn)
        flag = False
        for x in range(size - 1):
            if sn[x] > sn[x + 1]:
                flag = True
                break
        if not flag: return N
        while x > 0 and sn[x - 1] == sn[x]: x -= 1
        y = len(sn) - x - 1
        return (N / (10 ** y)) * (10 ** y) - 1

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%