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]`，最值之和 = 2+4+6 = 12
- 长度为2的子数组：`[1,2]`, `[2,3]`，最值之和 = 3+5 = 8
- 总计 = 20
核心思路：单调双端队列（Monotonic Deques）
这道题的关键在于避免枚举所有子数组。我们采用贡献法结合单调栈来高效计算：
1. 对于每个位置 `i`，维护以 `i` 结尾的所有合法子数组（长度 ≤ k）的最大值之和 `subarrays_max_sum`，以及最小值之和 `subarrays_min_sum`
2. 使用两个单调双端队列 `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 代码
```python
from collections import deque
class Solution:
def minMaxSubarraySum(self, nums: list[int], k: int) -> int:
subarrays_max_min_sum = 0
# 格式: [idx, num, shares]
# shares 表示该数值作为多少个以当前位置结尾的合法子数组的 max/min
max_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):
# 当前窗口的起始索引（保证子数组长度不超过 k）
start_idx = max(0, end_idx - k + 1)
# ========== 窗口边界控制：移除超出窗口范围的贡献 ==========
if start_idx > 0:
# 最大值栈：前端元素的共享次数减1，因为它"服务"的子数组少了一个
max_stack[0][2] -= 1
subarrays_max_sum -= max_stack[0][1] # 减去该元素的值
# 如果前端元素已完全滑出窗口，移除它
if max_stack[0][0] < start_idx:
max_stack.popleft()
# 最小值栈同理
min_stack[0][2] -= 1
subarrays_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 变成了 num
subarrays_max_sum += (num - prev_num) * prev_shares
max_stack.append([end_idx, num, max_shares])
# ========== 维护最小值单调栈（递增栈） ==========
min_shares = 1
subarrays_min_sum += num
while min_stack and min_stack[-1][1] >= num:
_, prev_num, prev_shares = min_stack.pop()
min_shares += prev_shares
subarrays_min_sum += (num - prev_num) * prev_shares
min_stack.append([end_idx, num, min_shares])
# ========== 累加当前位置的所有贡献 ==========
subarrays_max_min_sum += subarrays_max_sum + subarrays_min_sum
return subarrays_max_min_sum
```
复杂度分析
- 时间复杂度：O(n)，每个元素最多入栈和出栈各一次
- 空间复杂度：O(n)，两个单调栈的空间
验证
已通过题目示例验证：
- `minMaxSubarraySum([1,2,3], 2)` → `20` ✓
- `minMaxSubarraySum([1,-3,1], 2)` → `-6` ✓