小于n的最大整数(贪心+回溯O(n))

ans = []

flag = False

def dfs(target, index, hashmap):

    global ans

    global flag

    if index == len(target):

        if ''.join(ans) == target:

            return

        flag = True

        return

    t = int(target[index])

    if hashmap[t] == t:

        ans.append(str(t))

        dfs(target, index + 1, hashmap)

        if flag:

            return

        ans.pop()

    if hashmap[t] < t and hashmap[t]:

        ans.append(str(hashmap[t]))

        for i in range(len(target) - index - 1):

            ans.append(str(hashmap[9]))

        flag = True

        return

    if hashmap[t - 1] > 0:

        ans.append(str(hashmap[t - 1]))

        for i in range(len(target) - index - 1):

            ans.append(str(hashmap[9]))

        flag = True

class Solution:

    def findMax():

        global ans

        ans = []

        flag = False

        n = str(523224)

        nums = [1, 2, 3, 4, 5]

        hashmap = collections.defaultdict(int)

        for i in range(1, 10):

            for j in nums:

                if j <= i:

                    hashmap[i] = j

        dfs(n, 0, hashmap)

        if not ans:

            print(''.join([str(nums[-1]) for i in range(len(n) - 1)]))

            return

        print(''.join(ans))