3420. Count Non-Decreasing Subarrays After K Operations
- Array
- Stack
- Segment Tree
- Sliding Window
- Monotonic Stack
Intuition
Operations only increase values, so the cheapest way to make a subarray non-decreasing is to raise each element to the largest value before it. The cost of nums[l..r] is Σ (max(nums[l..i]) - nums[i]) for i in l..r.
That cost only grows when the window extends to the right, and only shrinks when an element is dropped from the left (prefix maxes can only go down). So for each left end, the valid right ends form a prefix l..R(l), and R(l) never increases as l moves left. That is a two-pointer setup.
The catch is updating the cost. Dropping the leftmost element changes the prefix max of a whole stretch after it, which is hard to undo. Adding an element on the left is easy, though: nums[l] becomes the prefix max of everything up to the next element bigger than it. So sweep l from right to left and only ever add on the left and remove on the right.
Approach
- Keep the window
nums[l..r]as a deque of blocks(value, count). Each block is a run of elements whose prefix max isvalue, and values increase from front to back. This is a monotonic stack of prefix maxima with run lengths attached. - For
lfromn - 1down to0:- Add
nums[l]on the left. Pop every front block withvalue <= nums[l]. Its elements now have prefix maxnums[l], so add(nums[l] - value) * countto the cost. Push one block(nums[l], 1 + popped counts). - Shrink from the right while
cost > k.nums[r]belongs to the back block, and its contribution isvalue - nums[r]. Subtract that, decrement the back block's count (pop it at zero), andr -= 1. - Count. Every right end in
l..rworks, so addr - l + 1.
- Add
rnever drops belowl, because a single element costs 0 andk >= 1.
Complexity
- Time: O(n). Each index is pushed once, merged away at most once, and removed from the right at most once.
- Space: O(n) for the blocks
Edge Cases
- Already non-decreasing: the cost stays 0 and every subarray counts,
n(n+1)/2 - One huge element followed by small ones (
[10, 1, 1, 1]withk = 1): the cost grows by about10^9per element, so the window shrinks to[10, 1]and then[10] - Equal values: popping uses
<=, so equal neighbours merge into one block and add 0 to the cost - The answer can reach about
n^2 / 2 ≈ 5 * 10^9, so it needslong - The cost before shrinking can reach about
10^5 * 10^9 = 10^14, so the cost needslongtoo. In Java,valis along[]so(nums[l] - val[head]) * cnt[head]is computed in 64 bits
Code
from collections import deque
from typing import List
class Solution:
def countNonDecreasingSubarrays(self, nums: List[int], k: int) -> int:
"""
3420. Count Non-Decreasing Subarrays After K Operations
Time: O(n)
Space: O(n)
"""
n = len(nums)
# Window nums[l..r] split into blocks, left to right. A block [value, count]
# is a run of count elements whose prefix max (from l) is value. Values
# strictly increase from front to back.
blocks = deque()
cost = 0 # sum of (prefix max - nums[i]) over the window
r = n - 1
ans = 0
for l in range(n - 1, -1, -1):
# nums[l] becomes the prefix max of every block it is >= to.
count = 1
while blocks and blocks[0][0] <= nums[l]:
value, c = blocks.popleft()
cost += (nums[l] - value) * c
count += c
blocks.appendleft([nums[l], count])
# Too expensive: drop elements from the right. nums[r] is in the
# last block, and leaving takes its (value - nums[r]) with it.
while cost > k:
cost -= blocks[-1][0] - nums[r]
blocks[-1][1] -= 1
if blocks[-1][1] == 0:
blocks.pop()
r -= 1
ans += r - l + 1
return ans/**
* 3420. Count Non-Decreasing Subarrays After K Operations
* Time: O(n)
* Space: O(n)
*/
class Solution {
public long countNonDecreasingSubarrays(int[] nums, int k) {
int n = nums.length;
// Window nums[l..r] split into blocks, left to right. Block i covers cnt[i]
// elements whose prefix max (from l) is val[i]. Values strictly increase
// from head to tail. Blocks are only pushed at the head, at most n times,
// so head counts down from n and never goes below 0.
long[] val = new long[n];
int[] cnt = new int[n];
int head = n, tail = n; // live blocks are [head, tail)
long cost = 0; // sum of (prefix max - nums[i]) over the window
int r = n - 1;
long ans = 0;
for (int l = n - 1; l >= 0; l--) {
// nums[l] becomes the prefix max of every block it is >= to.
int count = 1;
while (head < tail && val[head] <= nums[l]) {
cost += (nums[l] - val[head]) * cnt[head];
count += cnt[head];
head++;
}
head--;
val[head] = nums[l];
cnt[head] = count;
// Too expensive: drop elements from the right. nums[r] is in the
// last block, and leaving takes its (value - nums[r]) with it.
while (cost > k) {
cost -= val[tail - 1] - nums[r];
if (--cnt[tail - 1] == 0) {
tail--;
}
r--;
}
ans += r - l + 1;
}
return ans;
}
}