Leetcode 2111. Minimum Operations to Make the Array K-Increasing [Python]

本文主要是介绍Leetcode 2111. Minimum Operations to Make the Array K-Increasing [Python]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

暴力求解subarray的LIS的方式在89个（89/92）TC处TLE

class Solution:def kIncreasing(self, arr: List[int], k: int) -> int:subset = []res = 0for i in range(0, k):temp = []j = iwhile j < len(arr):temp.append(arr[j])j += kres += len(temp) - self.LIS(temp)return resdef LIS(self, arr):if not arr:return 0res = [1 for _ in range(len(arr))]for i in range(len(arr)):for j in range(i):if arr[j] <= arr[i]:res[i] = max(res[i], res[j]+1)return max(res)

这里可以注意到，LIS的求解是n**2的，可以改进为二分搜索的版本来做右插入。这里是非严格递增的，所以用右边二分插入，用新元素从右侧的替换第一个比当前新元素大的数字。

class Solution:def kIncreasing(self, arr: List[int], k: int) -> int:subset = []res = 0for i in range(0, k):temp = []j = iwhile j < len(arr):temp.append(arr[j])j += kres += len(temp) - self.LIS(temp) #找到LIS长度，剩下的元素需要替换。subarray总长度-LISreturn resdef LIS(self, arr):if not arr:return 0res = [float('inf') for _ in range(len(arr))] #设置全无限大的同大小的array；for i in range(len(arr)):idx = bisect.bisect_right(res, arr[i]) #遍历subarray，逐步从右侧替换第一个遍历元素大的res内元素。res[idx] = arr[i]for pos in range(len(res)-1, -1, -1):if res[pos] != float('inf'):return pos + 1 #返回被替换的元素的个数。return 0