Skip to content

Latest commit

 

History

History
193 lines (148 loc) · 6.44 KB

0738.单调递增的数字.md

File metadata and controls

193 lines (148 loc) · 6.44 KB

欢迎大家参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们收益!

738.单调递增的数字

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

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

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

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

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

示例 3: 输入: N = 332 输出: 299

说明: N 是在 [0, 10^9] 范围内的一个整数。

暴力解法

题意很简单,那么首先想的就是暴力解法了,来我替大家暴力一波,结果自然是超时!

代码如下:

class Solution {
private:
    bool checkNum(int num) {
        int max = 10;
        while (num) {
            int t = num % 10;
            if (max >= t) max = t;
            else return false;
            num = num / 10;
        }
        return true;
    }
public:
    int monotoneIncreasingDigits(int N) {
        for (int i = N; i > 0; i--) {
            if (checkNum(i)) return i;
        }
        return 0;
    }
};
  • 时间复杂度:O(n * m) m为n的数字长度
  • 空间复杂度:O(1)

贪心算法

题目要求小于等于N的最大单调递增的整数,那么拿一个两位的数字来举例。

例如:98,一旦出现strNum[i - 1] > strNum[i]的情况(非单调递增),首先想让strNum[i - 1]--,然后strNum[i]给为9,这样这个整数就是89,即小于98的最大的单调递增整数。

这一点如果想清楚了,这道题就好办了。

局部最优:遇到strNum[i - 1] > strNum[i]的情况,让strNum[i - 1]--,然后strNum[i]给为9,可以保证这两位变成最大单调递增整数

全局最优:得到小于等于N的最大单调递增的整数

但这里局部最优推出全局最优,还需要其他条件,即遍历顺序,和标记从哪一位开始统一改成9

此时是从前向后遍历还是从后向前遍历呢?

从前向后遍历的话,遇到strNum[i - 1] > strNum[i]的情况,让strNum[i - 1]减一,但此时如果strNum[i - 1]减一了,可能又小于strNum[i - 2]。

这么说有点抽象,举个例子,数字:332,从前向后遍历的话,那么就把变成了329,此时2又小于了第一位的3了,真正的结果应该是299。

所以从前后向遍历会改变已经遍历过的结果!

那么从后向前遍历,就可以重复利用上次比较得出的结果了,从后向前遍历332的数值变化为:332 -> 329 -> 299

确定了遍历顺序之后,那么此时局部最优就可以推出全局,找不出反例,试试贪心。

C++代码如下:

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string strNum = to_string(N);
        // flag用来标记赋值9从哪里开始
        // 设置为这个默认值,为了防止第二个for循环在flag没有被赋值的情况下执行
        int flag = strNum.size();
        for (int i = strNum.size() - 1; i > 0; i--) {
            if (strNum[i - 1] > strNum[i] ) {
                flag = i;
                strNum[i - 1]--;
            }
        }
        for (int i = flag; i < strNum.size(); i++) {
            strNum[i] = '9';
        }
        return stoi(strNum);
    }
};
  • 时间复杂度:O(n) n 为数字长度
  • 空间复杂度:O(n) 需要一个字符串,转化为字符串操作更方便

总结

本题只要想清楚个例,例如98,一旦出现strNum[i - 1] > strNum[i]的情况(非单调递增),首先想让strNum[i - 1]减一,strNum[i]赋值9,这样这个整数就是89。就可以很自然想到对应的贪心解法了。

想到了贪心,还要考虑遍历顺序,只有从后向前遍历才能重复利用上次比较的结果。

最后代码实现的时候,也需要一些技巧,例如用一个flag来标记从哪里开始赋值9。

其他语言版本

Java:

class Solution {
    public int monotoneIncreasingDigits(int N) {
        String[] strings = (N + "").split("");
        int start = strings.length;
        for (int i = strings.length - 1; i > 0; i--) {
            if (Integer.parseInt(strings[i]) < Integer.parseInt(strings[i - 1])) {
                strings[i - 1] = (Integer.parseInt(strings[i - 1]) - 1) + "";
                start = i;
            }
        }
        for (int i = start; i < strings.length; i++) {
            strings[i] = "9";
        }
        return Integer.parseInt(String.join("",strings));
    }
}

Python:

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        a = list(str(n))
        for i in range(len(a)-1,0,-1):
            if int(a[i]) < int(a[i-1]):
                a[i-1] = str(int(a[i-1]) - 1)
                a[i:] = '9' * (len(a) - i)  #python不需要设置flag值,直接按长度给9就好了
        return int("".join(a)) 

Go:

Javascript:

var monotoneIncreasingDigits = function(n) {
    n = n.toString()
    n = n.split('').map(item => {
        return +item
    })
    let flag = Infinity
    for(let i = n.length - 1; i > 0; i--) {
        if(n [i - 1] > n[i]) {
            flag = i
            n[i - 1] = n[i - 1] - 1
            n[i] = 9
        }
    }

    for(let i = flag; i < n.length; i++) {
        n[i] = 9
    }

    n = n.join('')
    return +n
};