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

福大大架构师每日一题

发布于 2022-06-04 10:18:47

4000

发布于 2022-06-04 10:18:47

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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
  }
}

执行结果如下：