Leetcode 45. Jump Game II（贪心）

45. Jump Game II

题目链接:https://leetcode.com/problems/jump-game-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.

题解:

这题写个O(n^2)的dp还是很容易的，似乎可以单调栈优化一波为O(n)。

这里说下我的吧，我的想法就是贪心:每次跳向能达到最远距离的点。

比较暴力的做法就是维护区间最大值，对于每个点，直接找它能跳到的符合贪心思想的点。这种做法应该是O(n*lgn)。

有比较巧妙的解法就是，对于每个能跳向最远距离的点，那么它必然能够跳出当前点的跳跃范围的。

比如一号点能跳到五号点，那二到五号点中肯定有点能够跳出这个范围。

那么我们就可以o(n)扫一遍，记录一下当前这个数的右边界，同时维护一下最大值以及这个最大值的右边界，当指针到达当前右边界时，最大值已经找完，更新下右边界以及答案就好了。

具体代码如下:

class Solution {
public:
    int n;
    int jump(vector<int>& nums) {
        n = nums.size();
        int r=min(nums[0],n-1);
        int step=0;
        int mx = r;
        for(int i=1;i<n;i++){
            mx=max(mx,i+nums[i]);
            if(i==r){
                step++;
                r=min(mx,n-1);
            }
        }
    return step;
    }
};