今日主要总结一下可以使用贪心算法解决的一道题目,738. 单调递增的数字
题目:738. 单调递增的数字
Leetcode题目地址
题目描述:
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。
给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增 。
示例 1:
输入: n = 10
输出: 9
示例 2:
输入: n = 1234
输出: 1234
示例 3:
输入: n = 332
输出: 299
提示:
0 <= n <= 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) {vector<int> mem;int flag = 0;int res = 0;for(; n; n /= 10){mem.emplace_back(n % 10);}if(mem.size() == 1 || mem.empty()) return n; for(int i = 1; i < mem.size(); i++){if(mem[i] > mem[i - 1]){mem[i] --;flag = i;}}for(int i = mem.size() - 1; i >= 0; i--){res *= 10;if(i >= flag) res += mem[i];else res += 9;}return res;}
};
写法二:int 转 string直接得到每一位的数字
class Solution {
public:int monotoneIncreasingDigits(int n) {string mem = to_string(n);int flag = mem.size();int res = 0;if(mem.size() == 1) return n; for(int i = mem.size() - 1; i > 0; i--){if(mem[i - 1] > mem[i]){mem[i - 1]--;flag = i;}}for(int i = flag; i < mem.size(); i++){mem[i] = '9';}return stoi(mem);}
};
第一种写法是当时自己第一遍写的,没有想到可以直接int 转 string得到每一位的数字
其实以上两种写法都可以,看哪个容易理解会写一种写法就行!
总结
本题只要想清楚个例,例如98,一旦出现strNum[i - 1] > strNum[i]的情况(非单调递增),首先想让strNum[i - 1]减一,strNum[i]赋值9,这样这个整数就是89。就可以很自然想到对应的贪心解法了。
想到了贪心,还要考虑遍历顺序,只有从后向前遍历才能重复利用上次比较的结果。
最后代码实现的时候,也需要一些技巧,例如用一个flag来标记从哪里开始赋值9。欢迎大家关注本人公众号:编程复盘与思考随笔(关注后可以免费获得本人在csdn发布的资源源码)