小旭讲解 LeetCode 738. 单调递增的数字
小旭讲解 LeetCode 738. 单调递增的数字

题目

LeetCode 738. 单调递增的数字

思路 – 贪心

观察数据范围 0 <= n <= 10^9,可知不能够用暴力枚举的方式。

为了保证当前数字非严格单调递减,以下方输入样例为例,直觉上,可以从左向右遍历,找到第一个不满足要求(即不是递增的)位置 i,将从 i 开始到结尾的所有字符改写成 9,同时向 i – 1 位进行借位即可。

此时,若 i – 1 被借位后导致当前数字变成了“单调递减”,那么将当前位改写成 9,继续向前借位,循环该步骤直到结束。

输入样例:

index: i-2  i-1   i   i+1
value:  3    3    2    1

answer: 2    9    9    9

代码

class Solution {
public:
    int monotoneIncreasingDigits(int N) {
        string nstr=to_string(N);
        int i=0;
        for (;i<nstr.size()-1;++i) {
            if (nstr[i]>nstr[i+1]) break;
        }
        if (i < nstr.size() - 1) {
            while (i >= 0 && nstr[i] > nstr[i+1]) {
                nstr[i] -= 1;
                i--;
            }
            for (i += 2;i<nstr.size();++i) nstr[i] = '9';
        }
        return stoi(nstr);
    }
};
欢迎分享,引用。若转载,请联系我,谢谢配合。
本文地址:https://qoogle.top/xiaoxu-tutorial-leetcode-738-monotone-increasing-digits/
0 0 vote
Article Rating
Subscribe
提醒
guest
1 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments

[…] 小旭讲解 LeetCode 738. 单调递增的数字 […]