Count Non-Decreasing Subarrays After K Operations
You are given an array nums of n integers and an integer k.
For each subarray of nums, you can apply up to k operations on it. In each operation, you increment any element of the subarray by 1.
Note that each subarray is considered independently, meaning changes made to one subarray do not persist to another.
Return the number of subarrays that you can make non-decreasing after performing at most k operations.
An array is said to be non-decreasing if each element is greater than or equal to its previous element, if it exists.
Example 1
Input
nums = [6,3,1,2,4,4], k = 7Output
17Out of all 21 possible subarrays of
nums, only [6, 3, 1], [6, 3, 1, 2], [6, 3, 1, 2, 4], and [6, 3, 1, 2, 4, 4] cannot be made non-decreasing after applying up to k = 7 operations, so the answer is 21 - 4 = 17.Example 2
Input
nums = [6,3,1,3,6], k = 4Output
12The subarray
[3, 1, 3, 6] along with all subarrays with three or fewer elements except [6, 3, 1] can be made non-decreasing after k operations, giving 1 + 5 + 4 + 2 = 12 valid subarrays.Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^9
- 1 <= k <= 10^9