跳跃游戏

📌 核心概念

跳跃游戏是贪心算法的经典应用，核心思想是维护当前能到达的最远位置。

贪心策略：每次跳跃都选择能让后续跳得更远的位置。

💻 算法实现

🎯 经典应用

💡 解题技巧

2. 优化技巧

# 优化1：提前终止
if farthest >= n - 1:
    break
 
# 优化2：删除已处理的值
del value_indices[arr[i]]
 
# 优化3：单调队列优化DP
from collections import deque
queue = deque()  # 维护窗口最值

📊 复杂度分析

问题	时间复杂度	空间复杂度	方法
跳跃游戏I	O(n)	O(1)	贪心
跳跃游戏II	O(n)	O(1)	贪心
跳跃游戏III	O(n)	O(n)	DFS/BFS
跳跃游戏IV	O(n)	O(n)	BFS优化
跳跃游戏V	O(n·d)	O(n)	DP
跳跃游戏VI	O(n)	O(k)	单调队列
跳跃游戏VII	O(n)	O(n)	前缀和

Go 代码

// 跳跃游戏I
func canJump(nums []int) bool {
    farthest := 0
 
    for i := 0; i < len(nums); i++ {
        if i > farthest {
            return false
        }
 
        farthest = max(farthest, i+nums[i])
 
        if farthest >= len(nums)-1 {
            return true
        }
    }
 
    return farthest >= len(nums)-1
}
 
// 跳跃游戏II
func jump(nums []int) int {
    n := len(nums)
    if n == 1 {
        return 0
    }
 
    jumps := 0
    currentEnd := 0
    farthest := 0
 
    for i := 0; i < n-1; i++ {
        farthest = max(farthest, i+nums[i])
 
        if i == currentEnd {
            jumps++
            currentEnd = farthest
 
            if currentEnd >= n-1 {
                break
            }
        }
    }
 
    return jumps
}
 
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

🎯 经典题目

题目	LeetCode	难度	关键点
跳跃游戏	55	中等	贪心维护最远
跳跃游戏II	45	中等	贪心边界
跳跃游戏III	1306	中等	DFS/BFS
跳跃游戏IV	1345	困难	BFS优化
跳跃游戏V	1340	困难	DP记忆化
跳跃游戏VI	1696	中等	单调队列
跳跃游戏VII	1871	中等	前缀和优化

---

返回：贪心算法