45 Jump Game II 跳躍游戲 II

Description:
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.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

You can assume that you can always reach the last index.

題目描述:
給定一個非負(fù)整數(shù)數(shù)組，你最初位于數(shù)組的第一個位置。

數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。

你的目標(biāo)是使用最少的跳躍次數(shù)到達(dá)數(shù)組的最后一個位置。

示例 :

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

說明:

假設(shè)你總是可以到達(dá)數(shù)組的最后一個位置。

思路:

貪心
每一次跳躍都選擇能跳到的最遠(yuǎn)距離
每一步更新 nums[i] + i
時間復(fù)雜度O(n), 空間復(fù)雜度O(1)

代碼:
C++:

class Solution 
{
public:
    int jump(vector<int>& nums) 
    {
        int result = 0, start = 0, end = 0;
        while (end < nums.size() - 1)
        {
            int best = end;
            for (int i = start; i <= end; i++) if (nums[i] + i > best) best = nums[i] + i;
            start = end + 1;
            end = best;
            ++result;
        }
        return result;
    }
};

Java:

class Solution {
    public int jump(int[] nums) {
        int result = 0, start = 0, end = 0;
        while (end < nums.length - 1) {
            int best = end;
            for (int i = start; i <= end; i++) if (nums[i] + i > best) best = nums[i] + i;
            start = end + 1;
            end = best;
            ++result;
        }
        return result;
    }
}

Python:

class Solution:
    def jump(self, nums: List[int]) -> int:
        result = start = end = 0
        while end < len(nums) - 1:
            best = end
            for i in range(start, end + 1):
                best = max(nums[i] + i, best)
            start, end, result = end + 1, best, result + 1
        return result