Leetcode736 单调递增的数字 (贪心策略)

Stella981
• 阅读 350

Leetcode736 单调递增的数字 (贪心策略)

贪心策略,从左到右,从高位到低位不断的分析数字,如果当前位是属于上升段,那么不断向右移动。如果移动到最右端,当前数字满足要去。

若否,那么将前一位-1,看看前一位是否满足要求,如果已经满足要求,那么将后面的位全部变为9,即得到满足要求的答案。

如果当前位-1不满足递增要求,说明要继续向前判断,直到满足要求后,将后面的所有位都变为9.

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string s = to_string(N);
        int n = s.size(), i = 1;
        while(i<n&&s[i]>=s[i-1]){
            i++;
        }
        if(i==n) return N;
        while(i>0&&s[i]<s[i-1]){
            s[i-1]--;
            i--;
        }
        i++;
        while(i<n){
            s[i++] = '9';
        }
        return stoi(s);
    }
};
点赞
收藏
评论区
推荐文章
Easter79 Easter79
3年前
synchronized 作为悲观锁,锁住了什么?
!(https://imgblog.csdnimg.cn/20200427085419625.jpg?xossprocessimage/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE2NDI2NjM,size_16,col
Stella981 Stella981
3年前
Android studio 顶部状态栏 的样式 顶部小刘海是否显示 颜色代码 颜色转换
Androidstudio顶部状态栏的样式!在这里插入图片描述(https://imgblog.csdnimg.cn/20200421105253767.jpg?xossprocessimage/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,t
Wesley13 Wesley13
3年前
K2 BPM_欢迎来到智能自动新纪元_全球领先的工作流引擎
!(https://imgblog.csdnimg.cn/2019072910092799.jpg?xossprocessimage/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0JlcnJ5MTIzNjU0,size_16,colo
Stella981 Stella981
3年前
Golang 文件上传下载服务(加入数据库)
!(https://imgblog.csdnimg.cn/20201212004719778.png?xossprocessimage/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d3eHkxOTk1,size_16,color_F
Stella981 Stella981
3年前
Leetcode 97交错字符
!(https://imgblog.csdnimg.cn/20200707182846168.png?xossprocessimage/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d3eHkxOTk1,size_16,color_F
Stella981 Stella981
3年前
Leetcode 572 另一个树的子树 : 递归转换为判断树是否相同
!(https://imgblog.csdnimg.cn/20200922212416167.png?xossprocessimage/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d3eHkxOTk1,size_16,color_F
Stella981 Stella981
3年前
Flutter 解答 StackOverflow问题 Page transition duration in flutter
!(https://imgblog.csdnimg.cn/2020100221425571.png?xossprocessimage/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTM0OTE4Mjk,size_16,colo
Wesley13 Wesley13
3年前
VirtualService资源详解
VirtualService资源详解学习目标!在这里插入图片描述(https://imgblog.csdnimg.cn/20200831115404401.jpg?xossprocessimage/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,te
Wesley13 Wesley13
3年前
C#游戏服务器遇到问题
!(https://imgblog.csdnimg.cn/20200508162537251.png?xossprocessimage/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzE1MjY3MzQx,size_16,col
Stella981 Stella981
3年前
Python发邮件
有图有真相!(https://imgblog.csdnimg.cn/20200511171317703.png?xossprocessimage/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2p4cTA4MTY,size_16,