【动态规划】LeetCode2111:使数组 K 递增的最少操作次数

作者推荐

[二分查找]LeetCode2040:两个有序数组的第 K 小乘积

本文涉及的基础知识点

二分查找算法合集
分组动态规划

题目

给你一个下标从 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

分析

时间复杂度

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<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<int, int> 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<int, int> 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;
}
};