题目
给你一个下标从 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 <= 105
1 <= arr[i], k <= arr.length
分析
时间复杂度
O(nlogn)，枚举每个元素，时间复杂度O(n)，每个元素二分查找O(logn)。
代码
原理
一，有多少对不符合递增，则至少需要多少次操作。arr[i]和arr[i+1]不符合，需要修改arr[i]或arr[i+1]。能否一次修改，同时解决两个数对，假定arr[i-1] > arr[i] > arr[i+1]，由于arr[i-1]>arr[i+1]，所以arr[i]无论如何都不可能大于等于arr[i-1]，同时小于等于arr[i+1]。
二，需要的操作数，可能大于非递增的对数。比如：4 1 3 ，4 1非递增，1 3递增。
三，操作次数等于=总元素数-最长递增序列的长度。假定最长子系列为：newNew[0]…newNew[n]。
四，第三只能说明是一个解，现在来证明是最优解： 假定arr2最优解，删掉修改过的元素，那么它一定是arr的子序列，且是递增的。此子系列越长，删除（操作）的元素越少。
| newNew[0]之前的元素 | 全部改成newNew[0] |
| newNew[n]之后的元素 | 全部改成newNew[n] |
| newNew[i]和newNew[i+1]的元素 | 全改成newNew[i] |
变量解释
| vLenMinEnd | vLenMinEnd[i]=x，在长度为i的子序列中，结尾的最小值为x |
核心代码
class Solution { public: int kIncreasing(vector<int>& arr, int k) { int iMaxLen = 0; for (int i = 0; i < k; i++) { vector<int> vLenMinEnd = { 0,arr[i] }; for (int j = i + k; j < arr.size(); j += k) { auto index = std::upper_bound(vLenMinEnd.begin(), vLenMinEnd.end(), arr[j])- vLenMinEnd.begin(); if (index >= vLenMinEnd.size()) { vLenMinEnd.emplace_back(arr[j]); continue; } vLenMinEnd[index] = min(vLenMinEnd[index], arr[j]); } iMaxLen += vLenMinEnd.size() - 1; } return arr.size()-iMaxLen; } };
测试用例
template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { vector arr; int k, res; { Solution slu; arr = { 12, 6, 12, 6, 14, 2, 13, 17, 3, 8, 11, 7, 4, 11, 18, 8, 8, 3 }, k = 1; auto res = slu.kIncreasing(arr, k); Assert(12, res); } { Solution slu; arr = { 5, 4, 3, 2, 1 }, k = 1; auto res = slu.kIncreasing(arr,k); Assert(4, res); } { Solution slu; arr = { 4,1,5,2,6,2 }, k = 2; auto res = slu.kIncreasing(arr, k); Assert(0, res); } { Solution slu; arr = { 4,1,5,2,6,2 }, k = 3; auto res = slu.kIncreasing(arr, k); Assert(2, res); }
//CConsole::Out(res);
}
2023年9月旧代码
class Solution { public: int kIncreasing(vector& arr, int k) { vector vSubArr(k); for (int i = 0; i < arr.size(); i++) { vSubArr[i%k].push_back(arr[i]); } int iRet = 0; for ( auto& v : vSubArr) { iRet += NeedChange(v, 0, v.size() ); } return iRet; } int NeedChange(vector& arr,int iLeft,int iRight) { std::map mValueNums; for (const auto& a : arr) { auto it = mValueNums.upper_bound(a); auto itTmp = it; const int iValue = ((mValueNums.begin() == it) ? 0 : (–itTmp)->second) + 1; if ((mValueNums.end() != it) && (it->second <= iValue)) { mValueNums.erase(it); } mValueNums[a] = iValue; } return arr.size() - mValueNums.rbegin()->second; } int m_iK; };
2023年9月第一版
class Solution { public: int kIncreasing(vector& arr, int k) { int iRet = 0; for (int turn = 0; turn < k; turn++) { std::map mEndLen; mEndLen[0] = 0; int iMaxLen = 0; for (int index = turn; index < arr.size(); index += k) { auto it = mEndLen.upper_bound(arr[index]); const int iLen = std::prev(it)->second+1; it = mEndLen.lower_bound(arr[index]); auto ij = it; for (; (ij != mEndLen.end()) && (ij->second <= iLen); ij++); mEndLen.erase(it, ij); mEndLen[arr[index]] = iLen; iMaxLen = max(iMaxLen, iLen); } iRet += iMaxLen; } return arr.size()- iRet; } };
2023年9月第二版
class Solution { public: int kIncreasing(vector& arr, int k) { int iRet = 0; for (int turn = 0; turn < k; turn++) { vector vValue; for (int index = turn; index < arr.size(); index += k) { auto it = std::upper_bound(vValue.begin(), vValue.end(),arr[index]); if (vValue.end() == it) { vValue.emplace_back(arr[index]); } else { *it = arr[index]; } } iRet += vValue.size(); } return arr.size()- iRet; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙，那算法就是他的是睛|
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
