738. 单调递增的数字

心已赠人 2022-11-27 15:41 127阅读 0赞

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/monotone-increasing-digits][https_leetcode-cn.com_problems_monotone-increasing-digits]  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1amlhbjIzMw_size_16_color_FFFFFF_t_70_pic_center]

注意333222这种情况 应该返回299999而不是332999

class Solution {
        
    public:
        int monotoneIncreasingDigits(int N) {
        
            string s = to_string(N);
    
            int i = 0;
            while(i < s.size()-1 && s[i] <= s[i+1]) ++i; //找到不递增的位置
            if(i == s.size()-1) return N; 
    
            s[i]--;//减一，
            while(i > 0 && s[i] < s[i-1] ) s[--i]--; //i往回检查，不满足递增就减一
            ++i; 
    
            for(; i < s.size(); ++i){
         //后面全置9
                s[i] = '9';
            }
    
            return stoi(s);
        }
    };

[https_leetcode-cn.com_problems_monotone-increasing-digits]: https://leetcode-cn.com/problems/monotone-increasing-digits
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1amlhbjIzMw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/99cbad781b0d4dac826ee713fcc3b40d.png

发表评论取消回复

表情：

评论列表（有 0 条评论，127人围观）

还没有评论，来说两句吧...

相关阅读

相关 738.单调自增的数字

738.单调自增的数字题干分析贪心算法解题总结代码实现 1. 创建String数组并多次使用Integer.parseInt方

小鱼儿/ 2023年10月16日 15:43/ 0 赞/ 20 阅读

相关 leetcode738 单调递增的数字

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时

浅浅的花香味﹌/ 2023年07月03日 02:52/ 0 赞/ 16 阅读

相关 C语言重构【738】单调递增的数字

文章目录所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)

刺骨的言语ヽ痛彻心扉/ 2022年12月28日 07:14/ 0 赞/ 181 阅读

相关算法-单调递增的数字

算法-单调递增的数字 1 题目概述 1.1 题目出处 https://leetcode-cn.com/problems/split-array-into-co

超、凢脫俗/ 2022年12月28日 06:27/ 0 赞/ 156 阅读

相关 letcode每日一题-单调递增的数字

题目描述如下： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV

落日映苍穹つ/ 2022年12月28日 06:25/ 0 赞/ 195 阅读

相关 738. 单调递增的数字

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时

心已赠人/ 2022年11月27日 15:41/ 0 赞/ 128 阅读

相关 leetcode 738 单调递增的数字

前言题目：[738. 单调递增的数字][738.] 参考题解：[单调递增的数字-代码随想录][-] -------------------- 提交代码错

以你之姓@/ 2022年09月15日 13:52/ 0 赞/ 129 阅读

相关 738 单调递增的数字（贪心）

1. 问题描述：给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。（当且仅当每个相邻位数上的数字 x 和 y 满足

向右看齐/ 2022年09月10日 05:27/ 0 赞/ 140 阅读

相关 leetcode 738. Monotone Increasing Digits 最大单调递增数字 + 找规律

Given a non-negative integer N, find the largest number that is less than or equal to N

青旅半醒/ 2022年06月03日 09:45/ 0 赞/ 161 阅读

相关 CodeForces - 714E + POJ - 3666 （dp严格单调递增与非严格单调递增）

POJ - 3666 ：此题是dp非严格单调递增的最小花费，要满足非严格递增，即后一个要大于等于前一个数，现在要求n个数的非严格递增前i个数的花费肯定是前i-1个数花费，再

本是古典何须时尚/ 2022年05月23日 04:20/ 0 赞/ 193 阅读