Given an array of positive integers target and an array initial of same size with all zeros.
Return the minimum number of operations to form a target array from initial if you are allowed to do the following operation:
- Choose any subarray from
initialand increment each value by one.
The answer is guaranteed to fit within the range of a 32-bit signed integer.
Example 1:
Input: target = [1,2,3,2,1] Output: 3 Explanation: We need at least 3 operations to form the target array from the initial array. [0,0,0,0,0] increment 1 from index 0 to 4 (inclusive). [1,1,1,1,1] increment 1 from index 1 to 3 (inclusive). [1,2,2,2,1] increment 1 at index 2. [1,2,3,2,1] target array is formed.
Example 2:
Input: target = [3,1,1,2] Output: 4 Explanation: (initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target).
Example 3:
Input: target = [3,1,5,4,2]
Output: 7
Explanation: (initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1]
-> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target).
Example 4:
Input: target = [1,1,1,1] Output: 1
Constraints:
1 <= target.length <= 10^51 <= target[i] <= 10^5
Solution:
If arr[i] < arr[i – 1], if we can generate arr[i] then we can always generate arr[i] with no extra cost.
e.g. [3, 2, 1] 3 < 2 < 1, [0,0,0] => [1,1,1] => [2, 2, 1] => [3, 2, 1]
So we only need to handle the case of arr[i] > arr[i – 1], we can reuse the computation, with extra cost of arr[i] – arr[i-1].
e.g. [2, 5]: [0,0] => [1, 1] => [2, 2], it takes 2 steps to cover arr[0].
[2,2] => [2, 3] => [2, 4] => [2, 5], takes another 3 steps (arr[1] – arr[0] / 5 – 2) to cover arr[1].
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 |
class Solution { public: int minNumberOperations(vector<int>& target) { int ans = target[0]; for (int i = 1; i < target.size(); ++i) ans += max(0, target[i] - target[i - 1]); return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment