45. 跳躍游戲 II

給定一個長度為?n?的?0 索引整數數組?nums。初始位置為?nums[0]。

每個元素?nums[i]?表示從索引?i?向后跳轉的最大長度。換句話說，如果你在索引?i?處，你可以跳轉到任意?(i + j)?處：

• 0 <= j <= nums[i]?且
• i + j < n

返回到達?n - 1?的最小跳躍次數。測試用例保證可以到達?n - 1。

class Solution {
public:int jump(vector<int>& nums) {int n = nums.size();int jumps = 0;int current_end = 0;int farthest = 0;for (int i = 0; i < n - 1; ++i) {farthest = max(farthest, i + nums[i]);if (i == current_end) {jumps++;current_end = farthest;if (current_end >= n - 1) {break;}}}        return jumps;}
};

處理邏輯是，在上一題的基礎上，記錄當前的跳躍次數以及當前所能達到的最遠點，只有在達到最遠點后，才增加跳躍次數。

這里的次數，其實記錄的是到達current_end所需最小次數，所以終止條件是，current_end大于等于n-1。

很容易陷入的牛角尖是，每一步都走最遠未必次數最少。這是正確的，但這里的算法邏輯是，在當前跳躍范圍內，盡可能探索下一步所能到達的最遠范圍，只有在不得不跳時，才次數加一。

在?jumps++時，算法并不關心“具體跳到哪里”，而是通過維護?current_end和?farthest隱式決定了跳躍策略??