Minimum Increment Operations to Make Array Beautiful
You are given a 0-indexed integer array nums having length n, and an integer k.
You can perform the following increment operation any number of times (including zero):
- Choose an index
iin the range[0, n - 1], and increasenums[i]by1.
An array is considered beautiful if, for any subarray with a size of 3 or more, its maximum element is greater than or equal to k.
Return an integer denoting the minimum number of increment operations needed to make nums beautiful.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1
Input
nums = [2,3,0,0,2], k = 4Output
3After 3 increments, every subarray of size 3 or more has maximum element equal to
k = 4, and fewer operations cannot make the array beautiful.Example 2
Input
nums = [0,1,3,3], k = 5Output
2Increasing
nums[2] twice makes it 5, so every subarray of size 3 or more has maximum element equal to k = 5, and fewer operations cannot make the array beautiful.Constraints
- 3 <= n == nums.length <= 10^5
- 0 <= nums[i] <= 10^9
- 0 <= k <= 10^9