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

輸入: [2,3,1,1,4]
輸出: 2
解釋: 從位置 0 到位置 1 跳 1 步, 然后跳 3 步到達最后一個位置。

解題思路：

貪心算法

代碼：

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

復(fù)雜度分析：

• 時間復(fù)雜度：O(N)，需要遍歷數(shù)組長度
• 空間復(fù)雜度：O(1)，只需要常數(shù)空間