2022-04-13：给你一个下标从 0 开始包含 n 个正整数的数组 arr ，和一个正整数 k

2022-04-13：给你一个下标从 0 开始包含 n 个正整数的数组 arr ，和一个正整数 k 。 如果对于每个满足 k <= i <= n-1 的下标 i ，都有 arr[i-k] <= arr[i] ，那么我们称 arr 是 K 递增 的。 比方说，arr = [4, 1, 5, 2, 6, 2] 对于 k = 2 是 K 递增的，因为： arr[0] <= arr[2] (4 <= 5) arr[1] <= arr[3] (1 <= 2) arr[2] <= arr[4] (5 <= 6) arr[3] <= arr[5] (2 <= 2) 但是，相同的数组 arr 对于 k = 1 不是 K 递增的（因为 arr[0] > arr[1]）， 对于 k = 3 也不是 K 递增的（因为 arr[0] > arr[3] ）。 每一次 操作 中，你可以选择一个下标 i 并将 arr[i] 改成任意 正整数。 请你返回对于给定的 k ，使数组变成 K 递增的 最少操作次数 。 力扣2111。

答案2022-04-13：

拆分成k个数组，分别求最长递增子序列，然后做差，最后求和。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
	arr := []int{5, 4, 3, 2, 1}
	k := 2
	ret := kIncreasing(arr, k)
	fmt.Println(ret)
}

func kIncreasing(arr []int, k int) int {
	n := len(arr)
	// a / b = 向下取整
	// a / b 向上取整 -> (a + b - 1) / b
	help := make([]int, (n+k-1)/k)
	ans := 0
	for i := 0; i < k; i++ {
		ans += need(arr, help, n, i, k)
	}
	return ans
}

// arr[start , start + k, start + 2k, start + 3k,....]
// 辅助数组help，为了求最长递增子序列，需要开辟的空间，具体看体系学习班
// 上面的序列，要改几个数，能都有序！
func need(arr, help []int, n, start, k int) int {
	j := 0
	size := 0
	for ; start < n; start, j = start+k, j+1 {
		size = insert(help, size, arr[start])
	}
	return j - size
}

func insert(help []int, size, num int) int {
	l := 0
	r := size - 1
	m := 0
	ans := size
	for l <= r {
		m = (l + r) / 2
		if help[m] > num {
			ans = m
			r = m - 1
		} else {
			l = m + 1
		}
	}
	help[ans] = num
	if ans == size {
		return size + 1
	} else {
		return size
	}
}

执行结果如下：

左神java代码