力扣第738题单调递增的数字 c++ 暴力超时贪心优化

题目

738. 单调递增的数字

中等

思路和解题方法一暴力（只看看就行）

从N开始递减，设当前数字为i。
对于当前数字i，我们需要检查它的每一位是否递增。
我们可以通过将数字i转换为字符串，然后逐位比较来判断是否递增。
如果当前位大于等于前一位，我们继续检查下一位。
如果当前位小于前一位，说明不满足递增条件，我们停止检查，并将i减1。
重复步骤2-5，直到找到满足条件的数字或i变为0。
如果找到满足条件的数字，返回该数字作为最大递增数字；否则返回0。

复杂度

时间复杂度:

O(n* m)

暴力解法的时间复杂度较高，为O(N*M)，其中N是给定数字N的大小，M是数字N的位数。因为要对每个数字进行逐位比较，所以需要遍历N个数字，对于每个数字需要检查其位数M次。

空间复杂度

O(M)

空间复杂度为O(M)，需要额外的存储空间来存储当前数字的字符串表示。

c++ 代码一

class Solution {
private:
    // 判断一个数字的各位上是否是递增
    bool checkNum(int num) {
        int max = 10; // 初始化最大值为10，表示还没有遇到任何数字
        while (num) { // 对数字的每一位进行遍历
            int t = num % 10; // 取出当前位的数字
            if (max >= t) max = t; // 如果当前位小于等于之前遇到的最大值，更新最大值
            else return false; // 如果当前位大于之前遇到的最大值，返回false
            num = num / 10; // 去掉最低位，继续处理下一位
        }
        return true; // 如果所有位都满足递增条件，返回true
    }
public:
    int monotoneIncreasingDigits(int N) {
        for (int i = N; i > 0; i--) { // 从大到小遍历数字
            if (checkNum(i)) return i; // 如果数字的各位递增，返回该数字
        }
        return 0; // 如果没有找到满足条件的数字，返回0
    }
};

思路和解题方法二贪心

首先，代码将给定数字N转换为字符串，方便后续操作。然后，使用一个变量flag来标记需要修改的位置，默认值为字符串的长度。
接下来，代码从字符串的末尾开始向前遍历，通过比较当前位和前一位的大小关系，找到第一个逆序对（即左边的数字大于右边的数字）。一旦找到逆序对，就将flag设置为当前位置，并将逆序对左边的数字减1。这样做的目的是保证当前位置及之后的所有位置都能取到9，从而满足递增条件。
最后，代码将flag位置及之后的所有位都设置为9，以确保得到的数字是小于等于N的最大递增数字。
最后，将修改后的字符串转换为整数并返回。

复杂度

时间复杂度:

O(M)

时间复杂度分析：

首先，我们将数字N转换为字符串表示，这需要O(M)的时间复杂度，其中M是数字N的位数。
在第一个for循环中，我们从后向前遍历字符串表示的数字，最多需要遍历M次。
在第一个for循环中，我们比较相邻的两个字符，并根据递减关系对前一位进行减1操作，最多需要比较M-1次。
在第二个for循环中，我们从标记位置开始，将后面的字符都设置为'9'，最多需要修改M-flag次。
最后，我们将修改后的字符串转换回整数，这需要O(M)的时间复杂度。

综上所述，总的时间复杂度为O(M)。

空间复杂度

O(M)

空间复杂度分析：

我们使用了一个字符串strNum来存储数字N的字符串表示，需要额外的O(M)的空间。
除此之外，没有使用其他额外的空间。

综上所述，总的空间复杂度为O(M)。

c++ 代码一

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string strNum = to_string(N); // 将给定数字N转换为字符串
        int flag = strNum.size(); // 标记赋值9的起始位置，默认为字符串长度，用于防止第二个for循环在flag没有被赋值的情况下执行

        // 从后往前遍历字符串，如果发现当前位大于前一位，则将前一位减1，并将flag设置为当前位置
        for (int i = strNum.size() - 1; i > 0; i--) {
            if (strNum[i - 1] > strNum[i]) {
                flag = i;
                strNum[i - 1]--; // 将前一位减1
            }
        }

        // 将flag位置及之后的所有位都设置为9，以保证最大递增数字的性质
        for (int i = flag; i < strNum.size(); i++) {
            strNum[i] = '9'; // 将当前位置及之后的所有位设置为9
        }

        return stoi(strNum); // 将字符串转换为整数并返回
    }
};

觉得有用的话可以点点赞，支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦 >人< 。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/109234.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！