heights of positive integers and a budget budget. Take any contiguous window of the array. One operation increases any single element of the window by 1, and you may perform at most budget operations.
A window qualifies if these operations can make it non-decreasing (every element at least as large as the one before it). Each window is handled on its own: changes made to one window do not carry over to another.
Return the number of qualifying windows.heights=[4, 2, 5, 1], budget=3 → 7
There are 10 windows. Only [5, 1] (cost 4), [2, 5, 1] (cost 4) and [4, 2, 5, 1] (cost 2 + 4 = 6) cannot be fixed. The answer is 10 − 3 = 7.
heights=[1, 2, 3], budget=1 → 6
The array is already non-decreasing, so all 6 windows qualify.
heights=[9, 1, 1], budget=8 → 5
The window [9, 1, 1] costs 8 + 8 = 16 and does not fit; the other 5 windows stay within the budget.
heights=[4, 2, 5, 1], budget=3
7
Run checks the first 3 tests in your browser. Submit checks all 135 tests on the server, hidden ones included.