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 是仅有的不满足 arr[i-3] <= arr[i] 的下标。
使数组 K 递增的方法之一是将 arr[3] 改为 4 ，将 arr[5] 改为 5 。
数组变为 [4,1,5,4,6,5] 。
可能有其他方法使数组变成 K 递增的，但没有任何一种方法需要的操作次数少于 2 次。

提示：

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i], k <= arr.length

解题思路

这个问题的核心思路是将原数组按照 k 进行分组，每个子序列都需要是非递减的。

分析步骤：

  1. 分组思想：根据 K 递增的定义，我们可以将数组分成 k 个子序列，第 i 个子序列包含所有下标模 k 等于 i 的元素。例如当 k=3 时，下标 0,3,6,… 为一组，下标 1,4,7,… 为一组，下标 2,5,8,… 为一组。

  2. 子问题转化：每个子序列都必须是非递减的。对于每个子序列，我们需要找到最少的修改次数使其变为非递减。

  3. 最优策略：对于每个子序列，我们应该保留最长的非递减子序列（LIS，但允许相等），然后修改其余元素。这样修改次数最少。

  4. LIS 求解：使用二分查找优化的方法求解最长非递减子序列的长度。注意这里允许相等，所以在二分查找时使用 upper_bound。

  5. 时间复杂度优化：整体时间复杂度为 O(n log n)，其中 n 是数组长度。

代码实现

class Solution {
public:
    int kIncreasing(vector<int>& arr, int k) {
        int n = arr.size();
        int operations = 0;
        
        // 对每个子序列分别处理
        for (int start = 0; start < k; start++) {
            vector<int> subseq;
            // 提取子序列
            for (int i = start; i < n; i += k) {
                subseq.push_back(arr[i]);
            }
            
            // 求最长非递减子序列长度
            int lis_len = getLIS(subseq);
            // 需要修改的元素个数
            operations += subseq.size() - lis_len;
        }
        
        return operations;
    }
    
private:
    int getLIS(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        vector<int> tails;
        for (int num : nums) {
            // 使用upper_bound因为允许相等
            auto it = upper_bound(tails.begin(), tails.end(), num);
            if (it == tails.end()) {
                tails.push_back(num);
            } else {
                *it = num;
            }
        }
        
        return tails.size();
    }
};

class Solution:
    def kIncreasing(self, arr: List[int], k: int) -> int:
        def get_lis_length(nums):
            """获取最长非递减子序列长度"""
            if not nums:
                return 0
            
            tails = []
            for num in nums:
                # 使用bisect_right因为允许相等
                pos = bisect.bisect_right(tails, num)
                if pos == len(tails):
                    tails.append(num)
                else:
                    tails[pos] = num
            
            return len(tails)
        
        n = len(arr)
        operations = 0
        
        # 对每个子序列分别处理
        for start in range(k):
            subseq = []
            # 提取子序列
            i = start
            while i < n:
                subseq.append(arr[i])
                i += k
            
            # 求最长非递减子序列长度
            lis_len = get_lis_length(subseq)
            # 需要修改的元素个数
            operations += len(subseq) - lis_len
        
        return operations

public class Solution {
    public int KIncreasing(int[] arr, int k) {
        int n = arr.Length;
        int operations = 0;
        
        // 对每个子序列分别处理
        for (int start = 0; start < k; start++) {
            List<int> subseq = new List<int>();
            // 提取子序列
            for (int i = start; i < n; i += k) {
                subseq.Add(arr[i]);
            }
            
            // 求最长非递减子序列长度
            int lisLen = GetLIS(subseq);
            // 需要修改的元素个数
            operations += subseq.Count - lisLen;
        }
        
        return operations;
    }
    
    private int GetLIS(List<int> nums) {
        if (nums.Count == 0) return 0;
        
        List<int> tails = new List<int>();
        foreach (int num in nums) {
            // 二分查找第一个大于num的位置
            int pos = BinarySearchUpper(tails, num);
            if (pos == tails.Count) {
                tails.Add(num);
            } else {
                tails[pos] = num;
            }
        }
        
        return tails.Count;
    }
    
    private int BinarySearchUpper(List<int> list, int target) {
        int left = 0, right = list.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (list[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

var kIncreasing = function(arr, k) {
    function longestIncreasingSubsequence(nums) {
        if (nums.length === 0) return 0;
        
        const tails = [];
        
        for (const num of nums) {
            let left = 0, right = tails.length;
            
            while (left < right) {
                const mid = Math.floor((left + right) / 2);
                if (tails[mid] <= num) {
                    left = mid + 1;
                } else {
                    right = mid;
                }
            }
            
            if (left === tails.length) {
                tails.push(num);
            } else {
                tails[left] = num;
            }
        }
        
        return tails.length;
    }
    
    let totalOperations = 0;
    
    for (let start = 0; start < k; start++) {
        const subsequence = [];
        
        for (let i = start; i < arr.length; i += k) {
            subsequence.push(arr[i]);
        }
        
        const lisLength = longestIncreasingSubsequence(subsequence);
        totalOperations += subsequence.length - lisLength;
    }
    
    return totalOperations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n log n)，其中 n 是数组长度。需要处理 k 个子序列，每个子序列平均长度为 n/k，求 LIS 的时间复杂度为 O((n/k) log (n/k))，总时间复杂度为 O(k × (n/k) log (n/k)) = O(n log (n/k)) = O(n log n)
空间复杂度O(n/k)，用于存储每个子序列和 LIS 算法中的 tails 数组

相关题目