題目描述

給你一個非負整數(shù)數(shù)組nums，你最初位于數(shù)組的第一個位置。
數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。
你的目標是使用最少的跳躍次數(shù)到達數(shù)組的最后一個位置。
假設(shè)你總是可以到達數(shù)組的最后一個位置。

示例

輸入：nums = [2,3,1,1,4]
輸出：2
解釋：跳到最后一個位置的最小跳躍數(shù)是 2。從下標為 0 跳到下標為 1 的位置，跳 1 步，然后跳 3 步到達數(shù)組的最后一個位置。

思路方法

這道題是典型的貪心算法，通過局部最優(yōu)解得到全局最優(yōu)解。以下兩種方法都是使用貪心算法實現(xiàn)，只是貪心的策略不同。

方法一：反向查找最初位置

我們的目標是到達數(shù)組的最后一個位置，因此我們可以考慮最后一步跳躍前所在的位置，該位置通過跳躍能夠到達最后一個位置。
如果有多個位置通過跳躍都能夠到達最后一個位置，那么我們應(yīng)該如何進行選擇呢？直觀上來看，我們可以使用貪心的選擇距離最后一個位置最遠的那個位置，也就是對應(yīng)下標最小的那個位置。因此我們可以從左到右遍歷數(shù)組，選擇第一個滿足要求的位置。
找到最后一步跳躍前所在的位置之后，以此類推，直到找到數(shù)組的開始的位置。

class Solution {
    public int jump(int[] nums) {
        int position = nums.length - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }
}

復雜度分析

• 時間復雜度：O(n^2)
• 空間復雜度：O(1)

方法二：正向查找到達最大位置

方法一雖然直觀，但是時間復雜度比較高，有沒有辦法降低時間復雜度呢？
如果我們貪心地進行正向查找，每次找到可到達的最遠位置，就可以在線性時間內(nèi)得到最少的跳躍次數(shù)。
例如，對于數(shù)組 [2,3,1,2,4,2,3]，初始位置是下標 0，從下標 0 出發(fā)，最遠可到達下標 2。下標 0 可到達的位置中，下標 1 的值是 3，從下標 1 出發(fā)可以達到更遠的位置，因此第一步到達下標 1。
從下標 1 出發(fā)，最遠可到達下標 4。下標 1 可到達的位置中，下標 4 的值是 4 ，從下標 4 出發(fā)可以達到更遠的位置，因此第二步到達下標 4。

class Solution {
    public int jump(int[] nums) {
       int length = nums.length;
       int end = 0;
       int maxPosition = 0;
       int steps = 0;
       for(int i=0;i<length-1;i++){
           maxPosition = Math.max(maxPosition,i+nums[i]);
           if(i==end){
               end = maxPosition;
               steps++;
           }
       }
       return steps;
    }
}

復雜度分析

• 時間復雜度：O(n)
• 空間復雜度：O(1)