leetcode：1187. 使数组严格递增【换or不换 + 二分贪心换最小增量 + dfs记忆化】

题目截图

题目分析

• arr2时用来替换的，先set去重再sort排序
• 逐为遍历arr1，如果第i位大于前一位，可以换or不换；如果小于等于，则必须换
• 换的话使用j = bisect_left(choices, pre)贪心找到增量最小的一位
• 如果j没有对应的choice元素，swap的值返回inf，否则dfs(i + 1, choices[j]) + 1
• 不换的话比较简单，但必须满足arr[i] > pre noswap = dfs(i + 1, arr[i])
• i == n return 0
• 记忆化搜索即可
• 注意初始化的pre使用-inf表示第一个的选择不受限制

ac code

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
        # 每一位都可以选择换or不换
        # 记忆化搜索换or不换,考虑前一个数
        # 从arr2中最贪心选一个更换
        choices = sorted(set(arr2))
        n = len(arr1)
        @cache
        def dfs(i, pre): # 表示当前为第i个，前一个值为pre，所需要更换的次数
            if i == n:
                return 0
            j = bisect_right(choices, pre) # choices中第一个大于pre的数
            swap = dfs(i + 1, choices[j]) + 1 if j < len(choices) else inf
            noswap = dfs(i + 1, arr1[i]) if arr1[i] > pre else inf
            return min(swap, noswap)
        ans = dfs(0, -inf)
        return ans if ans != inf else -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

总结

• 换or不换问题
• dfs(i,pre)表示当前arr1在第i位，且前一个为pre的情况下，使得后续数组递增的最小操作数
• 注意考虑换or不换
• 换的话二分必须找到对应最小增量位置，否则inf
• 不换的话必须arr[i] > pre，否则inf
• 选择换或者不换的最小者即可