题目回顾 LCP 09 最小跳跃次数给定数组 jump 初始在下标 0。每次操作二选一1. 向右跳到 i jump[i] 若超出数组长度则通关2. 向左跳到 [0, i-1] 任意位置。求最小操作步数。正确思路BFS 左边界优化避免超时普通BFS向左遍历会重复入队用 left 指针标记左侧已经处理过的区域每个位置只入队一次时间复杂度 O(n)。Python3 标准提交写法类方法pythonfrom collections import dequefrom typing import Listclass Solution:def minJump(self, jump: List[int]) - int:n len(jump)visited [False] * nq deque()q.append(0)visited[0] Truestep 0left 0 # 左侧已遍历的右边界while q:size len(q)for _ in range(size):cur q.popleft()# 向右跳nxt cur jump[cur]if nxt n:return step 1if not visited[nxt]:visited[nxt] Trueq.append(nxt)# 向左批量处理 [left, cur-1]while left cur:if not visited[left]:visited[left] Trueq.append(left)left 1step 1return -1样例测试pythons Solution()print(s.minJump([2,5,1,1,1,1])) # 输出 3核心要点1. 层序 BFS 保证第一次到达终点就是最小步数2. left 指针避免左侧节点重复入队解决暴力向左遍历的超时问题3. 向右跳直接计算目标位置超出数组立即返回步数1。
