給定一個(gè)非負(fù)整數(shù)數(shù)組踪危，你最初位于數(shù)組的第一個(gè)位置雇寇。數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長(zhǎng)度黍少。使用最少跳躍次數(shù)達(dá)到數(shù)組最后一個(gè)位置行剂。
輸入: [2,3,1,1,4]
輸出: 2
解釋: 從位置 0 到位置 1 跳 1 步, 然后跳 3 步到達(dá)最后一個(gè)位置。
解題思路：
貪心算法
代碼：
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ù)雜度分析：
- 時(shí)間復(fù)雜度：O(N)牍蜂，需要遍歷數(shù)組長(zhǎng)度
- 空間復(fù)雜度：O(1)漾根，只需要常數(shù)空間
