Kimi LeetCode 3420. 统计 K 次操作以内得到非递减子数组的数目 C++实现

📅 2026/6/30 22:44:28 👁️ 次浏览

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

相关新闻