力扣:738. 单调递增的数字(贪心)

2023-12-28 21:33:14

题目:

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

给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增 。

示例 1:

输入: n = 10
输出: 9
示例 2:

输入: n = 1234
输出: 1234
示例 3:

输入: n = 332
输出: 299

提示:

0 <= n <= 109

思路:

题意

首先先理解题意是什么,
给定一个整数n 要求返回一个从左往右单调递增的整数(后一位也可以等于前一位),并且n要尽可能的大(在<=n中最大且满足条件)
例:n = 1234
n本来就是从左往右单增,所以直接返回n本身1234
例:n = 322
要想n从左往右单增,则百位的3必须减1,此时百位3确定下来了,十位和个位是单增(包括等于)但222不是最大,最大是299,所以十位的2和个位的2要变成9

题意如果想清楚了,这道题就好办了。

此时是从前向后遍历还是从后向前遍历呢?
从前向后遍历的话,举个例子,数字:332,从前向后遍历的话,那么就把变成了329,此时2又小于了第一位的3了,真正的结果应该是299。
那么从后向前遍历,就可以重复利用上次比较得出的结果了,从后向前遍历332的数值变化为:332 -> 329 -> 299

确定了遍历顺序之后,那么此时局部最优就可以推出全局,找不出反例,试试贪心。

这里需要注意一点
题目中给出的n是整型,需要转化成字符型,字符型不能直接±

完整代码:

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        n = str(n)  # 将整数转换为字符串方便处理
        flag = len(n)  # 初始化标志位为字符串长度
        # 从后向前遍历字符串
        for i in range(len(n) - 1, 0, -1):
            # 如果当前数字比前一个数字小,说明需要修改前一个数字
            if n[i] < n[i - 1]:
                flag = i  # 更新标志位为当前位置i
                # 将前一个数字减1,然后将后面的数字都变为9
                n = n[: i - 1] + str(int(n[i - 1]) - 1) + n[i:]
        # 将标志位后面的所有数字都变为9
        for i in range(flag, len(n)):
            n = n[:i] + '9' + n[i + 1:]
        return int(n)  # 返回处理后的结果

暴力法(超时,但也是一个思路):

class Solution:
    def checkNum(self, num):
        max_digit = 10
        # 逐个提取num的各个位上的数字
        while num:
            digit = num % 10
            # 如果当前位的数字小于等于max_digit,则更新max_digit为当前位的数字
            if max_digit >= digit:
                max_digit = digit
            else:
                return False
            num //= 10
        return True

    def monotoneIncreasingDigits(self, N):
        # 从N开始递减到1
        for i in range(N, 0, -1):
            # 对每个数字调用checkNum方法进行检查
            if self.checkNum(i):
                return i
        return 0

复杂度分析:

  • 时间复杂度:O(n),n 为数字长度
  • 空间复杂度:O(n),需要一个字符串,转化为字符串操作更方便

文章来源:https://blog.csdn.net/2301_77160836/article/details/135277281
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。