45. 跳躍游戲 II

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

示例:

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

解析:

對(duì)于每一步，都能確定下一步能跳到的最遠(yuǎn)位置。這個(gè)最遠(yuǎn)位置可作為下一步的邊界。在到達(dá)這一步的邊界時(shí)，更新下一步的邊界為：這一步內(nèi)能跳到的最遠(yuǎn)位置。

貪心思想

局部最優(yōu)即為全局最優(yōu)。

此題只需向前看一步，選擇下一步能到達(dá)的位置中：能走的更遠(yuǎn)的那個(gè)，此位置即為全局最優(yōu)。例如：
下標(biāo) 0 可到達(dá)的位置中，下標(biāo) 1 的值是 3，從下標(biāo) 1 出發(fā)可以達(dá)到更遠(yuǎn)的位置，因此第一步到達(dá)下標(biāo) 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;

    }
};