題目描述
給定一個長度為 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]。
題目分析
在分析此題之前，可以先回顧下LeetCode 刷題 [C++] 第55題.跳躍游戲
再結合本體題意，本題依然是使用貪心算法的思想來分析：
- 依然是先構造一個表示能跳躍到的最大位置max_jump_pos，初始值為0；
- 遍歷數組：若當前值的下標小于等于max_jump_pos，表示能夠從前面的某個元素跳躍到當前位置，接下來比較當前元素值+當前元素位置是否大于max_jump_pos，若大于則更新max_jump_pos，否則，不更新max_jump_pos；
- 另外，我們再維護一個當前能夠到達的最大下標位置，記為邊界。更新該值時機：從左至右遍歷數組過程中，訪問到邊界元素時，更新邊界并將跳躍次數增加1。即在邊界區間內（包括邊界自身）一定發生了一次跳躍，且只有一次。
- 不要訪問最后一個元素，因為在這之前，我們的邊界一定大于等于最后一個位置，否則就無法跳躍到最后一個位置。如果訪問最后一個元素，可能會多增加一次不必要的跳躍次數。
Code
class Solution {
public:int jump(vector<int>& nums) {int max_jump_pos = 0, size = nums.size(), win_end = 0, step = 0;for (int i = 0; i < size - 1; ++i) {if (max_jump_pos >= i) {max_jump_pos = max(max_jump_pos, i + nums[i]);if (win_end == i) {win_end = max_jump_pos;++step;}}}return step;}
};
)
