2022-04-13：给你一个下标从 0 开始包含 n 个正整数的数组 arr ，和一个正整数 k 。 如果对于每个满足 k ＜= i ＜= n-1 的下标 i ，都有 arr[i-k] ＜= arr

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代码

2022-04-13：给你一个下标从 0 开始包含 n 个正整数的数组 arr ，和一个正整数 k 。 如果对于每个满足 k ＜= i ＜= n-1 的下标 i ，都有 arr[i-k] ＜= arr的相关教程结束。