題目描述

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A =[2,3,1,1,4]
The minimum number of jumps to reach the last index is2. (Jump1step from index 0 to 1, then3steps to the last index.)

• 思路
  求在一個(gè)數(shù)組中，值為對應(yīng)的最大可走步數(shù)，初始在0位置，最少幾步可以到達(dá)最后一個(gè)位置。
  遞歸等方法寫的都超時(shí)，后來看別人的題解才知道其他方法。遍歷此數(shù)組，定義一個(gè)變量cur記錄當(dāng)前位置可走的最遠(yuǎn)位置，還有一個(gè)變量last記錄上一跳躍到的位置可到達(dá)的最遠(yuǎn)位置。
  當(dāng)當(dāng)前位置大于之前記錄的最遠(yuǎn)位置時(shí)，表示永遠(yuǎn)走不到此位置則退出；
  當(dāng)當(dāng)前位置大于last時(shí)，表示上次跳躍到的位置剛好跳不到現(xiàn)在的位置，需要跳躍。此時(shí)遞增步數(shù)，更新last值為上個(gè)位置（即剛好可以跳到的位置）可以跳到的最遠(yuǎn)位置。
  最后更新當(dāng)前可走的最遠(yuǎn)距離cur。
  貪心的思想，由于每次跳躍時(shí)都是達(dá)到當(dāng)前所能走到的最遠(yuǎn)位置（再不跳就永遠(yuǎn)不會到達(dá)后面的位置了），所以最后得出的結(jié)果是最少的跳躍步數(shù)。

public class Solution {
    public int jump(int[] A) {
        if(A == null || A.length == 0)
            return -1;
        if(A.length == 1)
            return 0;
        
        int cnt = 0; //跳躍步數(shù)
        int cur = 0; //當(dāng)前所能跳躍的最遠(yuǎn)距離
        int last = 0; //上一次跳躍點(diǎn)所能到達(dá)的最遠(yuǎn)距離
        for(int i=0; i<A.length; i++){
            if(i > cur) //不可能跳到當(dāng)前位置時(shí)退出
                return -1;
            
            if(i > last){ //不要和下面的語句順序反了
                last = cur;
                cnt ++;
            }
            
            cur = Math.max(cur, i + A[i]); //記錄當(dāng)前可達(dá)的最遠(yuǎn)距離
        }
        
        return cnt;
    }
}