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

以下是 LeetCode 3420. 统计 K 次操作以内得到非递减子数组的数目 的 Python3 实现。---解题思路这道题的核心是 从右往左滑动窗口 单调队列时间复杂度 O(n)空间复杂度 O(n)。关键观察1. 单调性如果一个子数组 [i, j] 可以在 k 次操作内变为非递减那么它的所有子数组如 [i1, j]、[i, j-1] 等也一定可以。这满足了双指针的单调性条件。2. 为什么从右往左 从左往右扩展窗口时移除左边元素会影响右边元素的依赖关系处理极其复杂。而从右往左时新元素在左边只会影响右边已在窗口中的元素加边操作比删边简单得多。3. 单调队列的作用队列中存储的是 [数值, 个数] 对按数值非递增排列。它表示当前窗口在调整为非递减后每个平台的高度和覆盖的原始元素个数。- 当新元素 num 进入窗口时它会吸收队列尾部所有比它小的平台因为这些平台必须被提升到至少 num 的高度才能非递减。- 操作次数增加量 (num - 小平台高度) × 小平台元素个数。4. 窗口收缩当操作次数超过 k 时从右侧移除元素。最右侧的元素被恢复为原始值操作次数相应减少。---Python3 完整代码pythonfrom typing import Listfrom collections import dequeclass Solution:def countNonDecreasingSubarrays(self, nums: List[int], k: int) - int:ans 0 # 最终答案cost 0 # 当前窗口调整为非递减所需的操作次数# 单调队列存储 [数值, 个数] 对按数值非递增顺序排列dq deque()# i: 窗口左端点从右往左移动# j: 窗口右端点只会向左收缩j len(nums) - 1for 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_countcost (num - next_num) * next_countdq.append([num, count])# 操作次数超限从右侧缩小窗口while cost k:rightmost_num, rightmost_count dq.popleft()cost - rightmost_num - nums[j]j - 1if rightmost_count 1:dq.appendleft([rightmost_num, rightmost_count - 1])# 以 i 为左端点[i, j] 范围内的所有子数组都满足条件ans j - i 1return 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.py](sandbox:///mnt/agents/output/leetcode_3420.py)