苏宁网站建设和推广策略,邢台做网站推广费用,小程序云开发费用,网站排版教程题目
738. 单调递增的数字
中等
相关标签
贪心 数学
当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时#xff0c;我们称这个整数是单调递增的。
给定一个整数 n #xff0c;返回 小于或等于 n 的最大数字#xff0c;且数字呈 单调递增 。 示例 1:
输入: n 1…题目
738. 单调递增的数字
中等
相关标签
贪心 数学
当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时我们称这个整数是单调递增的。
给定一个整数 n 返回 小于或等于 n 的最大数字且数字呈 单调递增 。 示例 1:
输入: n 10
输出: 9示例 2:
输入: n 1234
输出: 1234示例 3:
输入: n 332
输出: 299提示:
0 n 109
思路和解题方法一 暴力 只看看就行 从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; // 如果当前位大于之前遇到的最大值返回falsenum 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); // 将字符串转换为整数并返回}
};觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
