贪心
解题思路
题目要求 返回 小于等于 整数 N 的整数，整数 N 的每一位是单调递增的，即 234 就是单调递增的；
- 例如：98 一旦出现 strNum[i - 1] > strNum[i] 的情况（非单调递增），首先想让 strNum[i - 1]- -，然后 strNum[i] 赋值为 9；
- 这样这个小于等于整数 N 的整数就是 89；
从前向后遍历：数字：332 从前向后遍历的话，那么就变成了 329 ，此时 2 又小于了第一位的 3 了，真正的结果应该是 299；
从后向前遍历：可以重复利用上次比较得出的结果，从后向前遍历 332 的数值变化为：332 -> 329 -> 299；
复杂度
-
时间复杂度：
O(n)，n 为数字长度； -
空间复杂度：
O(n)，需要一个字符串，转化为字符串操作更方便；
代码实现
var monotoneIncreasingDigits = function (n) {
n = [...n.toString()].map(item => +item);
let flag = Infinity; // 标记被修改的位置
// 从后向前遍历
for (let i = n.length - 1; i > 0; i--) {
// 后一位 < 前面一位
if (n[i - 1] > n[i]) {
flag = i;
n[i - 1]--;
n[i] = 9;
}
}
// flag 标记被修改的位置，从 flag 处向后都是 9
for (let i = flag; i < n.length; i++) {
n[i] = 9;
}
return +n.join('');
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 56. 合并区间
上一篇
评论
