舞钢市做网站开发的公司,推广类网站,东丰网站建设,网站建设有模板吗力扣题目链接
class Solution {
public:int monotoneIncreasingDigits(int N) {string strNum to_string(N);// flag用来标记赋值9从哪里开始// 设置为这个默认值#xff0c;为了防止第二个for循环在flag没有被赋值的情况下执行int flag strNum.size();for (int i strNum.…力扣题目链接
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);}
};一开始还没搞懂题目什么意思。
贪心算法思路不难想但代码不好写LeetCode:738.单调自增的数字_哔哩哔哩_bilibili
去看一下视频就明白了。 贪心算法
题目要求小于等于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
确定了遍历顺序之后那么此时局部最优就可以推出全局找不出反例试试贪心。 自己的思路
1.判断输入的数是否满足增序若满足输出本身。
2.为方便遍历将int数字转化为string类型
3.遍历从后向前如果前一个大于后一个进行处理
将前一位减1flag之后都变成9
4.最后返回变成int型
