Kimi 思考 LeetCode 3430. 最多 K 个元素的子数组的最值之和 Python3实现

这是 LeetCode 3430. Maximum and Minimum Sums of at Most Size K Subarrays最多 K 个元素的子数组的最值之和的 Python3 实现。题目理解给定整数数组 nums 和正整数 k要求计算所有长度不超过 k 的子数组的 最大值 最小值 的总和。例如 nums [1,2,3], k 2- 长度为1的子数组[1], [2], [3]最值之和 246 12- 长度为2的子数组[1,2], [2,3]最值之和 35 8- 总计 20核心思路单调双端队列Monotonic Deques这道题的关键在于避免枚举所有子数组。我们采用贡献法结合单调栈来高效计算1. 对于每个位置 i维护以 i 结尾的所有合法子数组长度 ≤ k的最大值之和 subarrays_max_sum以及最小值之和 subarrays_min_sum2. 使用两个单调双端队列 max_stack 和 min_stack 来追踪这些子数组的极值3. 队列中每个元素存储 [索引, 数值, 共享次数]其中 共享次数 表示该数值作为多少个以当前结尾的子数组的极值窗口边界控制当窗口滑动时start_idx max(0, i - k 1)需要移除超出窗口范围的贡献- 从队列前端减去被移出窗口的子数组的共享次数- 如果前端元素的索引已不在窗口内则 popleft()单调性维护以最大值栈为例当新元素 num 到来时- 如果栈顶元素的值 ≤ num则 num 会取代栈顶元素成为更多子数组的最大值- 将栈顶元素的 共享次数 转移给 num并调整总和subarrays_max_sum (num - prev_num) * prev_shares最小值栈的逻辑对称栈顶 ≥ num 时弹出。Python3 代码pythonfrom collections import dequeclass Solution:def minMaxSubarraySum(self, nums: list[int], k: int) - int:subarrays_max_min_sum 0# 格式: [idx, num, shares]# shares 表示该数值作为多少个以当前位置结尾的合法子数组的 max/minmax_stack: deque[list[int]] deque([])subarrays_max_sum 0 # 以当前位置结尾的所有合法子数组的最大值之和min_stack: deque[list[int]] deque([])subarrays_min_sum 0 # 以当前位置结尾的所有合法子数组的最小值之和for end_idx, num in enumerate(nums):# 当前窗口的起始索引保证子数组长度不超过 kstart_idx max(0, end_idx - k 1)# 窗口边界控制移除超出窗口范围的贡献 if start_idx 0:# 最大值栈前端元素的共享次数减1因为它服务的子数组少了一个max_stack[0][2] - 1subarrays_max_sum - max_stack[0][1] # 减去该元素的值# 如果前端元素已完全滑出窗口移除它if max_stack[0][0] start_idx:max_stack.popleft()# 最小值栈同理min_stack[0][2] - 1subarrays_min_sum - min_stack[0][1]if min_stack[0][0] start_idx:min_stack.popleft()# 维护最大值单调栈递减栈 max_shares 1 # 新元素至少作为单元素子数组 [num] 的最大值subarrays_max_sum num # 先加上单元素子数组的贡献# 栈顶元素值 当前值则当前值会取代它成为更多子数组的最大值while max_stack and max_stack[-1][1] num:_, prev_num, prev_shares max_stack.pop()max_shares prev_shares # 继承被弹出元素的共享次数# 调整总和这些子数组的最大值从 prev_num 变成了 numsubarrays_max_sum (num - prev_num) * prev_sharesmax_stack.append([end_idx, num, max_shares])# 维护最小值单调栈递增栈 min_shares 1subarrays_min_sum numwhile min_stack and min_stack[-1][1] num:_, prev_num, prev_shares min_stack.pop()min_shares prev_sharessubarrays_min_sum (num - prev_num) * prev_sharesmin_stack.append([end_idx, num, min_shares])# 累加当前位置的所有贡献 subarrays_max_min_sum subarrays_max_sum subarrays_min_sumreturn subarrays_max_min_sum复杂度分析- 时间复杂度O(n)每个元素最多入栈和出栈各一次- 空间复杂度O(n)两个单调栈的空间验证已通过题目示例验证- minMaxSubarraySum([1,2,3], 2) → 20 ✓- minMaxSubarraySum([1,-3,1], 2) → -6 ✓