優質博文：IT-BLOG-CN
一、題目
給定一個長度為n的0索引整數數組nums。初始位置為nums[0]。每個元素nums[i]表示從索引i向前跳轉的最大長度。換句話說，如果你在nums[i]處，你可以跳轉到任意nums[i + j]處:
0 <= j <= nums[i]
i + j < n
返回到達nums[n - 1]的最小跳躍次數。生成的測試用例可以到達nums[n - 1]。
示例 1:
輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數是2。從下標為0跳到下標為1的位置，跳1步，然后跳3步到達數組的最后一個位置。
示例 2:
輸入: nums = [2,3,0,1,4]
輸出: 2
1 <= nums.length <= 104
0 <= nums[i] <= 1000
題目保證可以到達nums[n-1]
二、代碼
反向查找出發位置： 我們的目標是到達數組的最后一個位置，因此我們可以考慮最后一步跳躍前所在的位置，該位置通過跳躍能夠到達最后一個位置。如果有多個位置通過跳躍都能夠到達最后一個位置，那么我們應該如何進行選擇呢？直觀上來看，我們可以「貪心」地選擇距離最后一個位置最遠的那個位置，也就是對應下標最小的那個位置。因此，我們可以從左到右遍歷數組，選擇第一個滿足要求的位置。找到最后一步跳躍前所在的位置之后，我們繼續貪心地尋找倒數第二步跳躍前所在的位置，以此類推，直到找到數組的開始位置。
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)，其中n是數組長度。有兩層嵌套循環，在最壞的情況下，例如數組中的所有元素都是1，position需要遍歷數組中的每個位置，對于position的每個值都有一次循環。
空間復雜度： O(1)，不需要額外的空間開銷。
正向查找可到達的最大位置： 方法一雖然直觀，但是時間復雜度比較高，有沒有辦法降低時間復雜度呢？
如果我們「貪心」地進行正向查找，每次找到可到達的最遠位置，就可以在線性時間內得到最少的跳躍次數。例如，對于數組[2,3,1,2,4,2,3]，初始位置是下標0，從下標0出發，最遠可到達下標2。下標0可到達的位置中，下標1的值是3，從下標1出發可以達到更遠的位置，因此第一步到達下標1。從下標1出發，最遠可到達下標4。下標1可到達的位置中，下標4的值是4，從下標4出發可以達到更遠的位置，因此第二步到達下標4。
在具體的實現中，我們維護當前能夠到達的最大下標位置，記為邊界。我們從左到右遍歷數組，到達邊界時，更新邊界并將跳躍次數增加1。在遍歷數組時，我們不訪問最后一個元素，這是因為在訪問最后一個元素之前，我們的邊界一定大于等于最后一個位置，否則就無法跳到最后一個位置了。如果訪問最后一個元素，在邊界正好為最后一個位置的情況下，我們會增加一次「不必要的跳躍次數」，因此我們不必訪問最后一個元素。
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)，其中n是數組長度。
空間復雜度： O(1)，不需要額外的空間開銷。
)
