网站建设流程总结,中信建设有限责任公司四川分公司,成都企业网站开发,gif表情包制作网站文章目录 738.单调递增的数字思路分析代码实现 738.单调递增的数字
题目链接#x1f525;#x1f525; 给定一个非负整数 N#xff0c;找出小于或等于 N 的最大的整数#xff0c;同时这个整数需要满足其各个位数上的数字是单调递增。 #xff08;当且仅当每个相邻位数上的… 文章目录 738.单调递增的数字思路分析代码实现 738.单调递增的数字
题目链接 给定一个非负整数 N找出小于或等于 N 的最大的整数同时这个整数需要满足其各个位数上的数字是单调递增。 当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时我们称这个整数是单调递增的。
示例 1: 输入: N 10 输出: 9
示例 2: 输入: N 1234 输出: 1234
示例 3: 输入: N 332 输出: 299 说明: N 是在 [0, 10^9] 范围内的一个整数。
思路分析
暴力解法会超时。 题目要求小于等于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代码如下
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);}
};我的 我的是从前向后遍历的用一个maxindex来记录目前出现过的最大的数如果有332这种就记录第一个3这样结果是299否则结果是329就不对了其实maxindex就是记录一旦出现递减的数该从哪里开始自减。
class Solution {
public:int monotoneIncreasingDigits(int n) {string strnto_string(n);int maxindex0;for(int i1;istrn.size();i){if(strn[i]strn[i-1]) maxindexi;if(strn[i]strn[i-1]){strn[maxindex]--;for(int jmaxindex1;jstrn.size();j) strn[j]9;}}int resultstoi(strn);return result;}
};
