单调递增的数字
单调递增的数字
WindRunnerMax
发布于 2020-12-18 11:05:36
发布于 2020-12-18 11:05:36
运行总次数：0
单调递增的数字
给定一个非负整数N，找出小于或等于N的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。当且仅当每个相邻位数上的数字x和y满足x <= y时，我们称这个整数是单调递增的。
示例
输入: N = 10
输出: 9输入: N = 1234
输出: 1234输入: N = 332
输出: 299题解
/**
* @param {number} N
* @return {number}
*/
var monotoneIncreasingDigits = function(N) {
let i = 1;
let num = N;
while(i*10 <= num){
// console.log(i, num);
// 每次取出两位
let n = ~~(num / i) % 100;
i = i * 10;
if(~~(n/10) > n %10) num = ~~(num / i) * i - 1;
// 例如 1332 第一次循环之后是 取整(1332 / 10) * 10 - 1 = 1330 - 1 = 1329
// 第二次循环就是 1300 - 1 = 1299
}
return num;
};思路
整体思路就是将数字当作字符串，从尾到头逆向遍历一遍，每次比较两位，如果后一个位置上的数小于前一个位置上的数，那么就将前边的数减一，并将后边的所有位都变为9，例如当我们遍历到了1323中比较32的这个位置上，此时3 > 2符合条件，那么我们就将3减一并将其后的数都变作9，即将其变为1299，直到遍历到头即可。通常来说可以把数字作为字符串来遍历处理，上面的题解是使用纯数字的方式去做，首先定义i作为标记记录遍历到到的位置，之后定义num作为待处理的数字，定义循环只要能够继续取出两位数就继续循环，这是循环的终止条件，此外能够使用乘法的地方就尽量不要使用除法，在js中int32如果不能够整除则会自动转双精度64，所以在很多地方都需要强制转数值为int32，之后取出两位数，这里~~是使用位运算强制转了整型，在之后将i * 10定义到下一位，如果低一位上的值大于大于高一位上的值，那么就将数值在第i位以后的值都变成0，然后减1即可达到上述的将此位减1以及之后的数字都变为9，可以参考上边的示例，在循环结束后返回处理的数字即可。
每日一题
https://github.com/WindrunnerMax/EveryDay参考
https://leetcode-cn.com/problems/monotone-increasing-digits/本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-12-15 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
