https://leetcode.com/problems/minimum-operations-to-make-the-array-k-increasing/
LIS的O(nlogn)解法

个人解答

  1. class Solution:
  2.     def kIncreasing(self, arr: List[int], k: int) -> int:
  3.         res = 0
  4.         for d in range(0, k):
  5.             min_tail = [] # min_tail[i]: min tail num with i-length LIS
  6.             for i in range(d, len(arr), k):
  7.                 if i == d:
  8.                     min_tail.append(arr[i])
  9.                     continue
  10.                 idx = bisect.bisect_right(min_tail, arr[i])
  11.                 if idx == len(min_tail):
  12.                     min_tail.append(arr[i])
  13.                 else:
  14.                     min_tail[idx] = arr[i]
  16.             res += len(arr) // k + int(d < len(arr) % k) - len(min_tail)
  17.         return res

题目分析

题目需要变通一下，其实就是求k个最长非降的子序列，不过题目给的数据范围大，常规的O(n^2)的解法超时，需要考虑O(nlogn)的解法

这里借鉴LIS题目中的解法：https://leetcode.com/problems/longest-increasing-subsequence/discuss/74824/JavaPython-Binary-search-O(nlogn)-time-with-explanation-time-with-explanation)

创建了一个tail数组，存储不同长度子序列的最小结尾数字，这样可以直接二分找到以当前数字结尾的最长子序列，妙哇！

以[4,5,6,3]为例：

  1. len = 1   :      [4], [5], [6], [3]   => tails[0] = 3
  2. len = 2   :      [4, 5], [5, 6]       => tails[1] = 5
  3. len = 3   :      [4, 5, 6]            => tails[2] = 6

那么，遇到一个新数字，只要二分这个[3,5,6]数组，找到对应位置：

  1. 如果比所有的都大，那么添到最后边
  2. 如果定位到某个位置i，那么更新i所在的值即可

最终，LIS就是这个数组的长度！