美文网首页
738. 单调递增的数字(Python)

738. 单调递增的数字(Python)

作者: 玖月晴 | 来源:发表于2020-12-14 20:19 被阅读0次

难度:★★★☆☆
类型:数组
方法:数学

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

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

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

示例 1:

输入: N = 10
输出: 9

示例 2:

输入: N = 1234
输出: 1234

示例 3:

输入: N = 332
输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。

解答

需要经过两次遍历。

第一次遍历,从最高位开始,寻找连续非递减子串的最大长度,找到不再连续非递减的位置。

第二次遍历,从第一次遍历找到的分界点开始向左遍历,做退位相减,直到最高位。

最后,将分界点以后的所有位置成9即可。

class Solution(object):
    def monotoneIncreasingDigits(self, N):
        S = list(map(int, str(N)))

        i = 0
        while i < len(S) - 1 and S[i] <= S[i+1]:
            i += 1
        while 0 <= i < len(S) - 1 and S[i] > S[i+1]:
            S[i] -= 1
            i -= 1
        S[i+2:] = [9] * (len(S) - i - 2)
        return int("".join(map(str, S)))

如有疑问或建议,欢迎评论区留言~

有关更多力扣中等题的python解决方案,请移步力扣中等题解析

相关文章

  • 每日一题20201215(738. 单调递增的数字)

    738. 单调递增的数字[https://leetcode-cn.com/problems/monotone-in...

  • 738. 单调递增的数字(Python)

    难度:★★★☆☆类型:数组方法:数学 力扣链接请移步本题传送门[https://leetcode-cn.com/p...

  • 738. 单调递增的数字

    题目: 当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。 给定一个整...

  • LeetCode 738. 单调递增的数字

    题目 当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。给定一个整数 ...

  • 贪心--单调递增的数字

    目录[https://www.jianshu.com/p/85e18c21317a] 题号[https://lee...

  • leetcode 738 单调递增的数字

    昨天卡爆的一道题!!!思路很简单,比较当前位和下一位关系,如果比下一位大,则将其减一,然后将后面的数字全变为九,卡...

  • 单调递增栈(monotonous increasing stac

    今天做leetcode时,发现两道题均用到了单调递增栈,遂进行学习。 什么是单调递增栈? 简单来说,单调递增栈就是...

  • 架构-分布式ID生成系统

    分布式ID特点: 唯一性 趋势递增 单调递增(严格递增)分布式系统中,如果不引用分布式锁,单调递增意义不大。 安全...

  • etcd和k8s的version

    etcd revision 全局单调递增的数字,任何key的增删改都会触发增加存在于resp的header中 cr...

  • 单调栈

    对应力扣题目-739. 每日温度 什么是单调栈? 单调递增栈,从栈底到栈顶依次递增(单调非递减栈:允许有相等) 单...

网友评论

      本文标题:738. 单调递增的数字(Python)

      本文链接:https://www.haomeiwen.com/subject/ycfrgktx.html