以下是 LeetCode 3420. 统计 K 次操作以内得到非递减子数组的数目 的 C++ 实现。
---
解题思路
这道题的核心是 从右往左滑动窗口 + 单调队列，时间复杂度 O(n)，空间复杂度 O(n)。
关键观察
1. 单调性：如果一个子数组 `[i, j]` 可以在 `k` 次操作内变为非递减，那么它的所有子数组（如 `[i+1, j]`、`[i, j-1]` 等）也一定可以。这满足了双指针的单调性条件。
2. 为什么从右往左？ 从左往右扩展窗口时，移除左边元素会影响右边元素的"依赖关系"，处理极其复杂。而从右往左时，新元素在左边，只会影响右边已在窗口中的元素，"加边"操作比"删边"简单得多。
3. 单调队列的作用：队列中存储的是 `<数值, 个数>` 对，按数值非递增排列。它表示当前窗口在调整为非递减后，每个"平台"的高度和覆盖的原始元素个数。
- 当新元素 `num` 进入窗口时，它会"吸收"队列尾部所有比它小的平台（因为这些平台必须被提升到至少 `num` 的高度才能非递减）。
- 操作次数增加量 = `(num - 小平台高度) × 小平台元素个数`。
4. 窗口收缩：当操作次数超过 `k` 时，从右侧移除元素。最右侧的元素被恢复为原始值，操作次数相应减少。
---
C++ 完整代码
```cpp
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
long long countNonDecreasingSubarrays(vector<int>& nums, int k) {
long long ans = 0;
long long cost = 0;
// 单调队列：存储 <数值, 个数> 对，按数值非递增顺序排列
deque<pair<int, long long>> dq;
// i: 窗口左端点（从右往左移动）
// j: 窗口右端点（只会向左收缩）
for (int i = nums.size() - 1, j = nums.size() - 1; i >= 0; --i) {
const int num = nums[i];
long long count = 1;
// 新元素 num 进入窗口，吸收队列尾部比它小的平台
while (!dq.empty() && dq.back().first < num) {
auto [nextNum, nextCount] = dq.back();
dq.pop_back();
count += nextCount;
cost += static_cast<long long>(num - nextNum) * nextCount;
}
dq.emplace_back(num, count);
// 操作次数超限，从右侧缩小窗口
while (cost > k) {
auto [rightmostNum, rightmostCount] = dq.front();
dq.pop_front();
cost -= static_cast<long long>(rightmostNum - nums[j]);
j--;
if (rightmostCount > 1) {
dq.emplace_front(rightmostNum, rightmostCount - 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.cpp](sandbox:///mnt/agents/output/leetcode_3420.cpp)
