以下是 LeetCode 3420. 统计 K 次操作以内得到非递减子数组的数目 的 Python3 实现。

---

解题思路

这道题的核心是 从右往左滑动窗口 + 单调队列，时间复杂度 O(n)，空间复杂度 O(n)。

关键观察

1. 单调性：如果一个子数组 `[i, j]` 可以在 `k` 次操作内变为非递减，那么它的所有子数组（如 `[i+1, j]`、`[i, j-1]` 等）也一定可以。这满足了双指针的单调性条件。

2. 为什么从右往左？ 从左往右扩展窗口时，移除左边元素会影响右边元素的"依赖关系"，处理极其复杂。而从右往左时，新元素在左边，只会影响右边已在窗口中的元素，"加边"操作比"删边"简单得多。

3. 单调队列的作用：队列中存储的是 `[数值, 个数]` 对，按数值非递增排列。它表示当前窗口在调整为非递减后，每个"平台"的高度和覆盖的原始元素个数。
   - 当新元素 `num` 进入窗口时，它会"吸收"队列尾部所有比它小的平台（因为这些平台必须被提升到至少 `num` 的高度才能非递减）。
   - 操作次数增加量 = `(num - 小平台高度) × 小平台元素个数`。

4. 窗口收缩：当操作次数超过 `k` 时，从右侧移除元素。最右侧的元素被恢复为原始值，操作次数相应减少。

---

Python3 完整代码

```python
from typing import List
from collections import deque

class Solution:
    def countNonDecreasingSubarrays(self, nums: List[int], k: int) -> int:
        ans = 0          # 最终答案
        cost = 0         # 当前窗口调整为非递减所需的操作次数
        
        # 单调队列：存储 [数值, 个数] 对，按数值非递增顺序排列
        dq = deque()
        
        # i: 窗口左端点（从右往左移动）
        # j: 窗口右端点（只会向左收缩）
        j = len(nums) - 1
        
        for i in range(len(nums) - 1, -1, -1):
            num = nums[i]
            count = 1
            
            # 新元素 num 进入窗口，吸收队列尾部比它小的平台
            while dq and dq[-1][0] < num:
                next_num, next_count = dq.pop()
                count += next_count
                cost += (num - next_num) * next_count
            
            dq.append([num, count])
            
            # 操作次数超限，从右侧缩小窗口
            while cost > k:
                rightmost_num, rightmost_count = dq.popleft()
                cost -= rightmost_num - nums[j]
                j -= 1
                if rightmost_count > 1:
                    dq.appendleft([rightmost_num, rightmost_count - 1])
            
            # 以 i 为左端点，[i, j] 范围内的所有子数组都满足条件
            ans += j - i + 1
        
        return ans
```

---

测试验证

输入    输出    说明    
`nums = [6,3,1,2,4,4], k = 7`    `17`    21 个子数组中 4 个不满足    
`nums = [6,3,1,3,6], k = 4`    `12`    官方示例 2    
`nums = [5], k = 0`    `1`    单元素天然非递减    
`nums = [1,2,3,4,5], k = 0`    `15`    已非递减，全部满足    
`nums = [5,4,3,2,1], k = 100`    `15`    k 足够大，全部满足    
`nums = [10,1,1,1], k = 2`    `7`    k 很小的情况    

下载完整代码：[leetcode_3420.py](sandbox:///mnt/agents/output/leetcode_3420.py)