3891. Minimum Increase to Maximize Special Indices
You are given an integer array nums of length n.
An index i (0 < i < n - 1) is special if nums[i] > nums[i - 1] and nums[i] > nums[i + 1].
You may perform operations where you choose any index i and increase nums[i] by 1.
Your goal is to:
- Maximize the number of special indices.
- Minimize the total number of operations required to achieve that maximum.
Return an integer denoting the minimum total number of operations required.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
public:
long long minIncrease(vector<int>& nums) {
int n = nums.size();
auto cost = [&](int i) {
return max({0ll, nums[i-1] - nums[i] + 1ll, nums[i+1] - nums[i] + 1ll});
};
if(n & 1) {
long long res = 0;
for(int i = 1; i < n; i += 2) res += cost(i);
return res;
}
vector<vector<long long>> pre(2, vector<long long>(n));
for(int i = 1; i < n - 1; i++) pre[i&1][i] = cost(i);
for(int i = 1; i < n; i++) pre[1][i] += pre[1][i-1];
for(int i = n - 2; i >= 0; i--) pre[0][i] += pre[0][i+1];
long long res = min({pre[0][0], pre[1][n-1]});
for(int i = 1; i < n - 2; i += 2) {
res = min(res, pre[1][i] + pre[0][i+2]);
}
return res;
}
};
|
