跳跃游戏

一 问题描述

给定一个非负整数数组 nums ，你最初位于数组的首个位置，每个元素值代表你在该位置可以跳跃的最大长度。判断是否能从首个位置跳到最后一个位置。

55. 跳跃游戏

二 解决方法

1 贪心法

分析

对于数组内任意位置 i 的元素 nums[i] ，存在 {i, i + 1, ... , i + nums[i]} 个位置可以达。当跳跃到这些位置中的某一个的时候，在新的位置上又会产生一系列新的可达位置。也就是说，我们需要判断最后一个元素位置是否存在在这些位置、或这些位置的可达位置中。

因为我们希望能达到的位置离数组最后一个位置越近越好，因此对于每一个位置的元素，我们都查找其最大的可达位置。如果所有的可达位置元素都不可达最后一个位置，那么数组也就无法从首个位置跳到最后一个位置。

最初位于数组的首个位置，也就是说在最初的最远可达位置是 0 。

代码

• 初始化可达最远位置为0

• 遍历数组

• 如果数组元素可达，更新最大可达位置

• 检查是否可达数组最后一个位置

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();							// 记录数组长度
        int maxIdx = 0;									// 初始化可达最远位置为0
        for (int i = 0; i < n; ++i) {					// 遍历数组
            if (i <= maxIdx) {							// 如果元素可达（可跳跃）
                maxIdx = max(maxIdx, i + nums[i]);		// 更新最大可达位置
                if (maxIdx >= n - 1) {					// 如果可达数组最后一个位置
                    return true;						// 返回true
                }
            }
        }
        return false;									// 遍历完数组仍不可达最后一个位置，返回false
    }
};

• 也可将条件 i < n 和 i <= maxIdx 合并，循环只遍历到可达的最大范围。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        int maxIdx = 0;
        for (int i = 0; i <= maxIdx; ++i) {
            maxIdx = max(maxIdx, i + nums[i]);
            if (maxIdx >= n - 1) {
                return true;
            }
        }
        return false;
    }
};

注意：如果可达的最大位置超过数组长度，那么将其作为下标访问数组，会出现数组越界的风险吗？

不会，在代码中只要可跳跃的最大位置大于等于数组长度-1，就会跳出循环。

三 总结

贪心算法是一种步步为营的策略，每一小步达到最优使得整体达到最优。