leetcode:2021.12.19周赛 变成递增数列的最少操作次数

思路：

想把间隔为k的转化成k个间隔为1的，然后再进行判断

核心函数lis的逻辑不大明晰

初步理解：D[]的构造过程中，比当前都大的话，那显然是不用处理的，所以到最后（就是没有操作）；其余的令D【i】变更都是一步操作

再次理解：lis是求最长上升子序列的，这里面估计是一种高级的写法，看不出dp的痕迹

再深入理解：这就是二分+贪心的LIS求法，其中这是不严格的LIS

题目链接：

原题

参见lis方法二：二分+贪心

我的LIS题解

代码：

class Solution:def kIncreasing(self, arr: List[int], k: int) -> int:def lis(A):D = []for a in A:i = bisect_right(D, a)if i == len(D):D.append(a)else:D[i] = areturn len(D)ans = 0for i in range(k):# 从头开始，按间隔取出对应的子数列A = arr[i::k]ans += len(A) - lis(A)return ans