45. 跳躍游戲 II
給定一個非負整數(shù)數(shù)組批什，你最初位于數(shù)組的第一個位置育灸。
數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度睡腿。
你的目標是使用最少的跳躍次數(shù)到達數(shù)組的最后一個位置买羞。
示例:
輸入: [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個位置的最小跳躍數(shù)是 `2`非春。
從下標為 0 跳到下標為 1 的位置柱徙，跳 `1` 步缓屠，然后跳 `3` 步到達數(shù)組的最后一個位置。
解析:
對于每一步护侮，都能確定下一步能跳到的最遠位置敌完。這個最遠位置可作為下一步的邊界。在到達這一步的邊界時羊初，更新下一步的邊界為：這一步內(nèi)能跳到的最遠位置滨溉。
貪心思想
局部最優(yōu)即為全局最優(yōu)。
此題只需向前看一步长赞，選擇下一步能到達的位置中：能走的更遠的那個业踏，此位置即為全局最優(yōu)。例如：
下標 0 可到達的位置中涧卵，下標 1 的值是 3勤家，從下標 1 出發(fā)可以達到更遠的位置，因此第一步到達下標 1柳恐。
代碼
class Solution {
public:
int jump(vector<int>& nums) {
int n=nums.size(), max_pos=0,end = 0;
int steps=0;
for(int i=0; i<n-1; ++i){
if(max_pos >=i){
max_pos = max(max_pos, i+nums[i]);
if(i==end){
++steps;
end = max_pos;
}
}
}
return steps;
}
};
