算法随想录| 738.单调递增的数字 ，968.监控二叉树 ， 总结

738.单调递增的数字?

代码随想录

思路

本来以为可以用回溯的，结果他不是求子集，回溯不了。

class Solution:
    def monotoneIncreasingDigits(self, N: int) -> int:
        # 将整数转换为字符串
        strNum = list(str(N))
        # 从右往左遍历字符串
        for i in range(len(strNum) - 1, 0, -1):
            # 如果当前字符比前一个字符小，说明需要修改前一个字符
            if strNum[i - 1] > strNum[i]:
                strNum[i - 1] = str(int(strNum[i - 1]) - 1)  # 将前一个字符减1
                # 将修改位置后面的字符都设置为9，因为修改前一个字符可能破坏了递增性质
                for j in range(i, len(strNum)):
                    strNum[j] = '9'

        # 将列表转换为字符串，并将字符串转换为整数并返回
        return int(''.join(strNum))

总结

这个贪心确实想不出来，不过一看答案就恍然大悟了，从右向左遍历，看数是否是递增的，如果不是就提前减一,把后面的数都变成9，这样他就是局部最优了。

其中“strNum = list(str(N))”和“int(''.join(strNum))”都是我想用的却写不出来的知识，要记。