[leetcode]贪心算法之Monotone Increasing Digits

淩亂°似流年 2021-09-28 12:00 260阅读 0赞

### 贪心算法之Monotone Increasing Digits ###

*  题干
 *  答案
 *  反思

# 题干 #

Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits.

(Recall that an integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.)

**Ex1:**

> Input: N = 10  
> Output: 9

**Ex2:**

> Input: N = 1234  
> Output: 1234

**Ex3:**

> Input: N = 332  
> Output: 299

# 答案 #

class Solution { 
    public:
        int monotoneIncreasingDigits(int N) { 
            string s="";
            
            while(N){ 
                s.push_back('0'+N%10);
                N/=10;
            }
            reverse(s.begin(),s.end());
            
            int size=s.size();
            
            for(int i=size-2;i>=0;i--){ 
                
                if(s[i]>s[i+1]){ 
                    s[i]=s[i]-1;
                    
                    for(int j=i+1;j<size;j++){ 
                        s[j]='9';
                    }
                }
            }
            
            return stoi(s);
        }
    };

# 反思 #

monotone Increasing的意思是单调上升，是不严格，意思是<=

因此从最后一位比较，逐渐降低位数，当降低位数后，后面的位数都可以填充’9’

解题过程中遇到的坑: 要把字符串而不是整数push\_back到字符串里

学习了函数  
stoi() 和 reverse()的用法

复习字符串和数字相互转换的方法：

数字->字符串

1.  sprintf
2.  stringstream
3.  itoa
4.  itos

字符串转数字：  
5. stringstream  
6. atoi  
7. stoi

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode 402. Remove K Digits (贪心)

题目意思: 给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。 ![watermark_type_ZmFuZ3poZW5naGVpdG

野性酷女/ 2023年05月30日 10:47/ 0 赞/ 15 阅读

相关 Leetcode——贪心算法之分发糖果

[参考][Link 1] 算法思路：我们只需要简单的两次遍历即可：把所有孩子的糖果数初始化为 1；先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更

刺骨的言语ヽ痛彻心扉/ 2023年01月10日 01:21/ 0 赞/ 157 阅读

相关贪心算法 leetcode编程题

1. [452. 用最少数量的箭引爆气球][452.] 在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上，气球直径的开始和结束坐标。由于它是水平的，所以纵坐

ゝ一世哀愁。/ 2022年12月23日 09:55/ 0 赞/ 194 阅读

相关 LeetCode题解-贪心算法

LeetCode题解-贪心算法文章目录 LeetCode题解-贪心算法 455. 分发饼干（简单） 435.无重叠区间（中等）

我就是我/ 2022年11月18日 02:03/ 0 赞/ 205 阅读

相关 LeetCode 之 Jump Game（贪心算法）

【问题描述】 Given an array of non-negative integers, you are initially positioned at the

ゝ一世哀愁。/ 2022年08月03日 11:47/ 0 赞/ 193 阅读

相关 leetcode 402. Remove K Digits 贪心算法 + DFS深度优先遍历 + stack

Given a non-negative integer num represented as a string, remove k digits from the numbe

矫情吗；*/ 2022年06月04日 07:29/ 0 赞/ 141 阅读

相关 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 阅读

相关 [leetcode]贪心算法之WiggleSubsequence

贪心算法之WiggleSubsequence 题目思考代码题目 [leetcode入口][leetcode] 思考而是维护两个变

客官°小女子只卖身不卖艺/ 2021年09月28日 14:52/ 0 赞/ 277 阅读

相关 [leetcode]贪心算法之Monotone Increasing Digits

贪心算法之Monotone Increasing Digits 题干答案反思题干 Given a non-negative integer

淩亂°似流年/ 2021年09月28日 12:00/ 0 赞/ 261 阅读

相关 [leetcode]贪心算法之jumpgame(一)(二)

贪心算法之jumpgameI、II I 题干 I 答案 I 反思 I II 题干II 答案I

一时失言乱红尘/ 2021年09月28日 12:00/ 0 赞/ 297 阅读