贪心算法：单调递增的数字
2021-03-08 11:31
标签：false 需要 incr ring 循环 one 顺序 全局 定时 通知：一些录友表示经常看不到每天的文章，现在公众号已经不按照发送时间推荐了，而是根据一些规则乱序推送，所以可能关注了「代码随想录」也一直看不到文章，建议把「代码随想录」设置星标哈，设置星标之后，每天就按发文时间推送了，Carl每天都是定时8:35发送的，嗷嗷准时！ 738.单调递增的数字 （当且仅当每个相邻位数上的数字 x 和 y 满足 x
示例 1: 示例 2: 示例 3: 说明: N 是在 [0, 10^9] 范围内的一个整数。 思路 代码如下： 例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]--，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。 这一点如果想清楚了，这道题就好办了。 局部最优：遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]--，然后strNum[i]给为9，可以保证这两位变成最大单调递增整数。 全局最优：得到小于等于N的最大单调递增的整数。 但这里局部最优推出全局最优，还需要其他条件，即遍历顺序，和标记从哪一位开始统一改成9。 此时是从前向后遍历还是从后向前遍历呢？ 从前向后遍历的话，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。 这么说有点抽象，举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。 所以从前后向遍历会改变已经遍历过的结果！ 那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299 确定了遍历顺序之后，那么此时局部最优就可以推出全局，找不出反例，试试贪心。 C++代码如下： 想到了贪心，还要考虑遍历顺序，只有从后向前遍历才能重复利用上次比较的结果。 最后代码实现的时候，也需要一些技巧，例如用一个flag来标记从哪里开始赋值9。 就酱，循序渐进学算法，认准「代码随想录」！ 贪心算法：单调递增的数字 标签：false 需要 incr ring 循环 one 顺序 全局 定时 原文地址：https://blog.51cto.com/15069438/2576225
给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。
输入: N = 10
输出: 9
输入: N = 1234
输出: 1234
输入: N = 332
输出: 299
暴力解法
题意很简单，那么首先想的就是暴力解法了，来我提大家暴力一波，结果自然是超时！
class Solution {
private:
bool checkNum(int num) {
int max = 10;
while (num) {
int t = num % 10;
if (max >= t) max = t;
else return false;
num = num / 10;
}
return true;
}
public:
int monotoneIncreasingDigits(int N) {
for (int i = N; i > 0; i--) {
if (checkNum(i)) return i;
}
return 0;
}
};
贪心算法
题目要求小于等于N的最大单调递增的整数，那么拿一个两位的数字来举例。
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
总结
本题只要想清楚个例，例如98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]减一，strNum[i]赋值9，这样这个整数就是89。就可以很自然想到对应的贪心解法了。
上一篇：扩展排序后重新编号
下一篇：本周小结！（贪心算法系列四）