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

以下是 LeetCode 3420. 统计 K 次操作以内得到非递减子数组的数目的 Java 实现。---解题思路这道题的核心是 从右往左滑动窗口 单调队列时间复杂度 O(n)空间复杂度 O(n)。关键观察1. 单调性如果一个子数组 [i, j] 可以在 k 次操作内变为非递减那么它的所有子数组如 [i1, j]、[i, j-1] 等也一定可以。这满足了双指针的单调性条件。2. 为什么从右往左 从左往右扩展窗口时移除左边元素会影响右边元素的依赖关系处理极其复杂。而从右往左时新元素在左边只会影响右边已在窗口中的元素加边操作比删边简单得多。3. 单调队列的作用队列中存储的是 数值, 个数 对按数值非递增排列。它表示当前窗口在调整为非递减后每个平台的高度和覆盖的原始元素个数。- 当新元素 num 进入窗口时它会吸收队列尾部所有比它小的平台因为这些平台必须被提升到至少 num 的高度才能非递减。- 操作次数增加量 (num - 小平台高度) × 小平台元素个数。4. 窗口收缩当操作次数超过 k 时从右侧移除元素。最右侧的元素被恢复为原始值操作次数相应减少。---Java 完整代码javaimport java.util.ArrayDeque;import java.util.Deque;class Solution {public long countNonDecreasingSubarrays(int[] nums, int k) {long ans 0;long cost 0;// 单调队列存储 数值, 个数 对按数值非递增顺序排列Dequeint[] dq new ArrayDeque();// i: 窗口左端点从右往左移动// j: 窗口右端点只会向左收缩for (int i nums.length - 1, j nums.length - 1; i 0; --i) {final int num nums[i];int count 1;// 新元素 num 进入窗口吸收队列尾部比它小的平台while (!dq.isEmpty() dq.peekLast()[0] num) {int[] last dq.pollLast();int nextNum last[0];int nextCount last[1];count nextCount;// 将 nextCount 个元素从 nextNum 提升到 num 的操作次数cost (long) (num - nextNum) * nextCount;}dq.offerLast(new int[]{num, count});// 操作次数超限从右侧缩小窗口while (cost k) {int[] first dq.pollFirst();int rightmostNum first[0];int rightmostCount first[1];// 移除最右边元素恢复为原始值 nums[j]cost - (long) (rightmostNum - nums[j]);j--;// 该平台还有剩余元素放回队列头部if (rightmostCount 1) {dq.offerFirst(new int[]{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 足够大全部满足下载完整代码[leetcode_3420.java](sandbox:///mnt/agents/output/leetcode_3420.java)