Input: arr =[5,4,3,2,1], k =1Output: 4Explanation: For k =1, the resultant array has to be non-decreasing.Some of the K-increasing arrays that can be formed are [5,_**6**_ ,_**7**_ ,_**8**_ ,_**9**_],[_**1**_ ,_**1**_ ,_**1**_ ,_**1**_ ,1],[_**2**_ ,_**2**_ ,3,_**4**_ ,_**4**_]. All of them require 4 operations.It is suboptimal to change the array to,for example,[_**6**_ ,_**7**_ ,_**8**_ ,_**9**_ ,_**10**_] because it would take 5 operations.It can be shown that we cannot make the array K-increasing in less than 4 operations.
Input: arr =[4,1,5,2,6,2], k =2Output: 0Explanation:
This is the same example as the one in the problem description.Here,for every index i where 2<= i <=5, arr[i-2]<=**** arr[i].Since the given array is already K-increasing, we do not need to perform any operations.
Input: arr =[4,1,5,2,6,2], k =3Output: 2Explanation:
Indices 3 and 5 are the only ones not satisfying arr[i-3]<= arr[i]for3<= i <=5.One of the ways we can make the array K-increasing is by changing arr[3] to 4 and arr[5] to 5.The array will now be [4,1,5,_**4**_ ,6,_**5**_].Note that there can be other ways to make the array K-increasing, but none of them require less than 2 operations.
The array can be split into k groups, each group containing elements at positions i, i+k, i+2k, etc. Each group must be non-decreasing for the whole array to be k-increasing. The minimum number of changes for each group is the group size minus the length of its longest non-decreasing subsequence.
classSolution {
public:int minOperations(vector<int>& arr, int k) {
int n = arr.size(), ans =0;
for (int i =0; i < k; ++i) {
vector<int> seq;
for (int j = i; j < n; j += k) seq.push_back(arr[j]);
vector<int> dp;
for (int x : seq) {
auto it = upper_bound(dp.begin(), dp.end(), x);
if (it == dp.end()) dp.push_back(x);
else*it = x;
}
ans += seq.size() - dp.size();
}
return ans;
}
};
classSolution {
funminOperations(arr: IntArray, k: Int): Int {
var ans = 0for (i in0 until k) {
val seq = mutableListOf<Int>()
var j = i
while (j < arr.size) {
seq.add(arr[j])
j += k
}
val dp = mutableListOf<Int>()
for (x in seq) {
val idx = dp.binarySearch(x + 1).let { if (it < 0) -it - 1elseit }
if (idx == dp.size) dp.add(x) else dp[idx] = x
}
ans += seq.size - dp.size
}
return ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
classSolution:
defminOperations(self, arr: list[int], k: int) -> int:
ans =0 n = len(arr)
for i in range(k):
seq = [arr[j] for j in range(i, n, k)]
dp = []
for x in seq:
idx = bisect.bisect_right(dp, x)
if idx == len(dp):
dp.append(x)
else:
dp[idx] = x
ans += len(seq) - len(dp)
return ans