1526: Minimum-Number-of-Increments-on-Subarrays-to-Form-a-Target-Array
Hard
table of contents
We can take a greedy approach to solving this question;
realise that at the index position i, we only have to
increment a subarray that starts at index
i if the previous value, target[i-1],
was smaller.
code
class Solution {
public:
int minNumberOperations(vector<int>& target) {
int ans = 0, prev = 0;
for (int& t : target) {
if (prev < t) {
ans += t-prev;
}
prev = t;
}
return ans;
}
};