C++, greedy solution


  • 0

    Here is my solution, I used 'upper' to keep track of the current position that has been updated

    class Solution {
    public:
        int jump(vector<int>& nums) {
            if (nums.size()==0) return 0;
            vector<int> jumps(nums.size(), 0);
            int upper = 0;
            for (int i=0; i<nums.size(); i++){
                if ((i+nums[i]) > upper){
                    for (int j=upper+1; j<=i+nums[i] && j<nums.size(); j++){
                        jumps[j] = jumps[i]+1;
                    }
                }
                if (i+nums[i]>=nums.size()) break;
                upper = max(upper, i+nums[i]);
            }
            return jumps[nums.size()-1];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.