使数组 K 递增的最少操作次数

难度: Hard

给你一个下标从 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 递增的 最少操作次数 。

示例 1：

输入：arr = [5,4,3,2,1], k = 1
输出：4
解释：
对于 k = 1 ，数组最终必须变成非递减的。
可行的 K 递增结果数组为 [5,6,7,8,9]，[1,1,1,1,1]，[2,2,3,4,4] 。它们都需要 4 次操作。
次优解是将数组变成比方说 [6,7,8,9,10] ，因为需要 5 次操作。
显然我们无法使用少于 4 次操作将数组变成 K 递增的。

示例 2：

输入：arr = [4,1,5,2,6,2], k = 2
输出：0
解释：
这是题目描述中的例子。
对于每个满足 2 <= i <= 5 的下标 i ，有 arr[i-2] <= arr[i] 。
由于给定数组已经是 K 递增的，我们不需要进行任何操作。

示例 3：

输入：arr = [4,1,5,2,6,2], k = 3
输出：2
解释：
下标 3 和 5 是仅有的 3 <= i <= 5 且不满足 arr[i-3] <= arr[i] 的下标。
将数组变成 K 递增的方法之一是将 arr[3] 变为 4 ，且将 arr[5] 变成 5 。
数组变为 [4,1,5,4,6,5] 。
可能有其他方法将数组变为 K 递增的，但没有任何一种方法需要的操作次数小于 2 次。

提示：

1 <= arr.length <= 10⁵
1 <= arr[i], k <= arr.length

Submission

运行时间: 162 ms

内存: 27.3 MB

class Solution:
    def kIncreasing(self, arr: List[int], k: int) -> int:
        def lis(arr):
            t = []
            for x in arr:
                idx = bisect_right(t, x)
                if idx == len(t):
                    t.append(x)
                else:
                    t[idx] = x
            return len(arr) - len(t)

        return sum(lis(arr[i::k]) for i in range(k))

Explain

本题解使用了最长递增子序列（LIS）的思想来解决问题。首先，对于每个下标 i（i < k），我们考虑以 i 为起点，间隔为 k 的子序列，这样可以得到 k 个子序列。对每个子序列，我们使用二分查找法求出其最长递增子序列的长度。由于我们需要将子序列变为递增，所以需要进行的操作次数等于子序列的长度减去其最长递增子序列的长度。最后，将所有子序列需要的操作次数相加，即为最终答案。

时间复杂度: O(n * log(n/k))

空间复杂度: O(n)

class Solution:
    def kIncreasing(self, arr: List[int], k: int) -> int:
        def lis(arr):
            t = []
            for x in arr:
                idx = bisect_right(t, x)
                if idx == len(t):
                    t.append(x)
                else:
                    t[idx] = x
            return len(arr) - len(t)

        return sum(lis(arr[i::k]) for i in range(k))

Explore

这个策略是基于题目的要求，即确保每个下标i（i < k）开始的、间隔为k的子序列需要单独递增。如果直接对整个数组操作，会忽略这种间隔的特殊要求，可能导致某些间隔的子序列不满足递增的条件。分解为k个子序列后，可以确保每个间隔k的子序列独立处理，从而符合题目的要求。

在求解最长递增子序列（LIS）时，使用二分查找来更新t数组中的元素可以帮助我们保持t数组尽可能的小，这是因为更新操作可以替换掉较大的数，使t数组的末尾元素更小，这有助于后续元素的添加。此外，这种方法可以确保t数组始终保持为LIS的一个潜在候选，即使它可能不是唯一的或最终的LIS。

通过确保每个子序列独立满足递增的条件，即每个从下标i (i < k) 开始，间隔为k的子序列都是递增的，从而整个数组自然满足k递增的条件。这是因为k递增的定义本质上要求从任一位置i开始的、间隔为k的子序列必须是递增的，所以单独确保每个这样的子序列是递增的，就能满足整个数组的k递增要求。

在这种情况下，最后的子序列可能会比其他子序列短，但这并不影响处理方式。我们仍然对这个短的子序列应用同样的最长递增子序列方法来求解需要减少的元素数量。由于这个子序列本身长度就短，其对总操作次数的影响相对较小。因此，无论数组的长度是否为k的倍数，该方法都是有效的。