北京专业做网站设计公司,杨凌网站开发,网页游戏网络游戏,国内比百度好的搜索引擎文章目录 738. 单调递增的数字题目描述思路贪心算法代码逻辑梳理#xff1a; 738. 单调递增的数字
题目描述
当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时#xff0c;我们称这个整数是单调递增的。
给定一个整数 n #xff0c;返回 小于或等于 n 的最大数字 738. 单调递增的数字
题目描述
当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时我们称这个整数是单调递增的。
给定一个整数 n 返回 小于或等于 n 的最大数字且数字呈 单调递增 。
示例 1: 输入: n 10 输出: 9 示例 2: 输入: n 1234 输出: 1234 示例 3: 输入: n 332 输出: 299 提示:
0 n 109
思路
题目要求小于等于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 - 1]减一了可能又小于strNum[i - 2]。
这么说有点抽象举个例子数字332从前向后遍历的话那么就把变成了329此时2又小于了第一位的3了真正的结果应该是299。
那么从后向前遍历就可以重复利用上次比较得出的结果了从后向前遍历332的数值变化为332 - 329 - 299
确定了遍历顺序之后那么此时局部最优就可以推出全局找不出反例试试贪心。
贪心算法
这段代码是C编写的用于解决寻找小于或等于给定整数且为单调递增的最大数字的问题。下面是对这段代码的详细注释
// 定义Solution类
class Solution {
public:// 主函数用于找到小于或等于n的最大单调递增数字int monotoneIncreasingDigits(int n) {// 将整数n转换成字符串s以便逐位处理string s to_string(n);// 初始化标志位flag为字符串s的长度用于标记从哪一位开始后面的数字都设置为9int flag s.size();// 从字符串的最后一位开始向前遍历寻找不满足单调递增的位置for(int i s.size() - 1; i 0; i--) {// 如果当前位的前一位大于当前位则需要进行调整if(s[i - 1] s[i]) {// 当前位的前一位减1以满足单调递增的条件s[i - 1] - 1;// 更新flag从当前位开始后面的数字都应该设置为9flag i;}}// 根据flag将flag位置及之后的所有位设置为9for(int i flag; i s.size(); i)s[i] 9;// 将处理后的字符串转换回整数并返回return stoi(s);}
};代码逻辑梳理
这个问题的关键在于找到从哪一位开始数字不再满足单调递增的条件并且如何调整这个数字及其后续的数字使得结果是小于等于n的最大单调递增数字。 字符串转换首先将整数n转换为字符串s这样可以便于逐位检查和修改数字。 反向遍历从字符串的最后一位开始向前遍历寻找第一个不满足单调递增的位置。这是通过比较当前位的前一位和当前位实现的。 调整数字当找到一个不满足条件的位置时将前一位数字减1并记录这个位置到flag中。这样做的原因是减小前一位数字后为了保证结果是最大的从当前位开始直到字符串末尾的所有数字都应该设置为9。 更新后续位根据flag将从flag开始到字符串末尾的所有位设置为9。 结果转换最后将修改后的字符串转换回整数返回。
这个解决方案巧妙地通过调整数字和后续位填充9的方式确保了得到的结果既是单调递增的又是小于等于原始数字n的最大值。
