MENU

LeetCode45. 跳跃游戏 II

July 5, 2018 • Read: 314 • LeetCode

image
还是以样例为例,[2,3,1,1,4],起点是nums[0] = 2,那么在nums[1] = 3和nums[2] = 1中我们应该选择哪个进行跳跃?很明显,应该选择nums[1] = 3,因为他的数值大,这样跳跃的范围就大。所以这道题的贪心规律就是:当前你在nums[i],下一步所跳的位置应该是nums[i]中范围内,数值最大的

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size() < 2)
            return 0;
        int current_max_index = nums[0];
        int pre_max_index = nums[0];
        int jump_min = 1;
        for(int i = 1;i < nums.size();i++){
            if(i > current_max_index){
                jump_min++;
                current_max_index = pre_max_index;
            }
            if(pre_max_index < nums[i] + i)
                pre_max_index = nums[i] + i;
        }
        return jump_min;
    }
};
最后编辑于: October 10, 2018
Archives Tip
QR Code for this page
Tipping QR Code