給你一個(gè)非負(fù)整數(shù)數(shù)組?nums?，你最初位于數(shù)組的?第一個(gè)下標(biāo)?。數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長度。判斷你是否能夠到達(dá)最后一個(gè)下標(biāo)，如果可以，返回?true?；否則，返回?false?。

示例?1：

輸入：nums = [2,3,1,1,4]
輸出：true
解釋：可以先跳 1 步，從下標(biāo) 0 到達(dá)下標(biāo) 1, 然后再從下標(biāo) 1 跳 3 步到達(dá)最后一個(gè)下標(biāo)。

示例?2：

輸入：nums = [3,2,1,0,4]
輸出：false
解釋：無論怎樣，總會(huì)到達(dá)下標(biāo)為 3 的位置。但該下標(biāo)的最大跳躍長度是 0 ， 所以永遠(yuǎn)不可能到達(dá)最后一個(gè)下標(biāo)。

>>思路和分析

示例1中，若站在元素3的位置，我究竟是跳一步還是跳兩步，還是跳三步呢？?因?yàn)檫@是至多跳三步，那我究竟跳幾步呢？然后我跳到下一個(gè)元素我又究竟要跳幾步呢？能否跳到終點(diǎn)呢？

如果沿著這個(gè)思路去想，那本題就很難想出來了。其實(shí)可以換一個(gè)維度，不去糾結(jié)于在數(shù)組中得到一個(gè)元素往后具體去跳幾步，我們只看覆蓋范圍。也就是說，在一開始站在起始位置，往后的覆蓋范圍就是覆蓋了兩步，然后站在元素3這個(gè)位置，往后的覆蓋范圍就是三步的覆蓋范圍。那么最終就把終點(diǎn)給覆蓋了。

只要在覆蓋范圍內(nèi)，那任何一個(gè)元素的下標(biāo)位置，都可以跳到，別管我是跳幾步，別管我是怎么跳的，我就是可以跳過來。那么這個(gè)問題就轉(zhuǎn)化為跳躍覆蓋范圍究竟可不可以覆蓋終點(diǎn)！

核心：怎么跳躍不重要，關(guān)鍵在覆蓋范圍

思路：每次移動(dòng)取最大跳躍步數(shù)（得到最大的覆蓋范圍），每移動(dòng)一個(gè)單位，就更新最大覆蓋范圍

>>貪心算法

• 局部最優(yōu)解：每次取最大跳躍步數(shù)（取最大覆蓋范圍）
• 整體最優(yōu)解：最后得到整體最大覆蓋范圍，看是否能到終點(diǎn)

局部最優(yōu)推出全局最優(yōu)，找不到反例，試試貪心！

C++代碼：

class Solution {
public:bool canJump(vector<int>& nums) {int cover = 0;if (nums.size() == 1) return true; // 只有一個(gè)元素，就是能達(dá)到for (int i = 0; i <= cover; i++) { // 注意這里是小于等于covercover = max(i + nums[i], cover);if (cover >= nums.size() - 1) return true; // 說明可以覆蓋到終點(diǎn)了}return false;}
};

• 時(shí)間復(fù)雜度: O(n)
• 空間復(fù)雜度: O(1)

參考和推薦文章、視頻

?代碼隨想錄 (programmercarl.com)

?貪心算法，怎么跳躍不重要，關(guān)鍵在覆蓋范圍 | LeetCode：55.跳躍游戲_嗶哩嗶哩_bilibili

來自代碼隨想錄的課堂截圖：