leetcode 45. Jump Game II

题目

Jump Game II

题目就是从位置0开始 跳到位置n-1， 每次在位置i 可以跳的最远位置为 i+nums[i]

思路和代码

参考自 leetcode most vote

The main idea is based on greedy. Let's say the range of the current jump is [curBegin, curEnd], curFarthest is the farthest point that all points in [curBegin, curEnd] can reach. Once the current point reaches curEnd, then trigger another jump, and set the new curEnd with curFarthest, then keep the above steps, as the following:

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