本文介绍一种基于优先队列（最小堆）的高效算法，用于在给定有序整数数组和目标阈值 limit 下，找出所有合法累加序列中 ≥limit 的最小和与最大和；关键约束是：累加必须从数组起始位置开始、不可跳过中间元素、允许重复使用当前及后续元素。
本文介绍一种基于优先队列（最小堆）的高效算法，用于在给定有序整数数组和目标阈值 limit 下，找出所有合法累加序列中 ≥limit 的最小和与最大和；关键约束是：累加必须从数组起始位置开始、不可跳过中间元素、允许重复使用当前及后续元素。
该问题本质是一个带约束的有向图路径搜索问题：数组索引构成节点，每一步可选择“停留在当前索引继续累加”或“前进到下一索引再累加”，目标是在首次达到或超过 limit 时，记录所有可行路径对应的和，并从中提取全局最小值与最大值。
核心约束解析
- ✅ 不可跳过元素：意味着累加序列必须由连续前缀（从 arr[0] 开始）的若干次扩展构成，即若当前在索引 i，下一步只能用 arr[i]（重复）或切换至 arr[i+1]（前进），但不能直接跳到 arr[i+2]。
- ✅ 允许重复使用：在索引 i 处可多次添加 arr[i]，直到决定前进。
- ✅ 首次达标即终止：一旦当前和 ≥ limit，该路径即为一个候选解，无需继续扩展。
上述约束排除了完全背包或子集和等经典模型——它不是任意组合，而是具有顺序依赖性的路径生成过程。
算法设计：Dijkstra 变体 + 双目标追踪
暴力递归易栈溢出且重复计算严重；动态规划难以定义状态维度（因路径长度无界）。最优解是采用最小堆驱动的状态空间搜索：
- 每个状态为 (current_sum, current_index, path)，按 current_sum 小顶堆排序，优先探索更小和；
- 使用 known 字典去重：键为 (sum, index)，避免相同和+位置的冗余路径；
- 遍历时对每个状态生成两个分支：
- 停留复用：sum += arr[i]，索引 i 不变；
- 前进切换：sum 不变，索引 i → i+1（仅当 i+1 < len(arr)）；
- 一旦 sum ≥ limit，立即更新 best_min 和 best_max，并终止该路径扩展。
⚠️ 注意：原题示例中 [100, 200, 300, 1000, 10000] 在递归方法中返回 10900 是错误的——因为 10000 单独已 ≥1000，但按约束必须从 arr[0]=100 开始累加，故 10000 无法被单独选取（除非先经过 100→200→300→1000→10000 序列，其和远超 10900）。正确最小和仍是 1000（10×100），最大和为 1900（100+200+300+300+1000），验证了算法对约束的严格遵守。
Python 实现（健壮版）
import heapq
from typing import Tuple, Optional, List
def min_max_limit_sum(arr: List[int], limit: int) -> Tuple[int, int]:
if not arr or limit <= 0:
raise ValueError("Invalid input: empty array or non-positive limit")
# State: (current_sum, index, path_tuple) — path_tuple for debugging, optional
heap = [(0, 0, ())] # Start at index 0 with sum 0
visited = set() # Memo: (sum, index)
best_min = float('inf')
best_max = float('-inf')
while heap:
s, i, path = heapq.heappop(heap)
# Skip if revisiting same (sum, index)
if (s, i) in visited:
continue
visited.add((s, i))
# If already >= limit, update results and skip expansion
if s >= limit:
best_min = min(best_min, s)
best_max = max(best_max, s)
continue
# Cannot proceed beyond array bounds
if i >= len(arr):
continue
# Branch 1: Use arr[i] again (stay at same index)
new_s1 = s + arr[i]
heapq.heappush(heap, (new_s1, i, path + (arr[i],)))
# Branch 2: Move to next index (advance)
if i + 1 < len(arr):
heapq.heappush(heap, (s, i + 1, path))
if best_min == float('inf') or best_max == float('-inf'):
raise ValueError(f"No valid sequence reaches or exceeds limit {limit}")
return best_min, best_max
# 测试用例验证
print(min_max_limit_sum([100, 200, 300, 1000], 1000)) # (1000, 1900)
print(min_max_limit_sum([3, 10, 15], 1000)) # (1000, 1014)关键优势与注意事项
- 时间复杂度：最坏为 O(K log K)，其中 K 是实际访问的状态数，远优于指数级递归；
- 空间可控：堆与 visited 集合仅存储必要状态，避免栈溢出；
- 正确性保障：通过 (sum, index) 去重 + 严格索引递进规则，彻底规避跳过元素或非法组合；
- 边界处理：显式校验空数组、非正 limit，提升鲁棒性；
- 扩展提示：如需返回具体路径，可保留 path 元组（示例中已注释说明）；若仅需数值，可移除路径存储以节省内存。
该方案将抽象约束转化为图搜索建模，结合堆的贪心特性与状态去重机制，在保证正确性的前提下实现高效求解，是解决此类“有序累积达标”问题的推荐范式。
