Simple c++ solution


  • 0
    N

    since the answer array is non-decreasing, wo can solve this problem in O(n) time and O(1) space

    class Solution {
    public:
        int jump(vector<int>& nums) {
            int u = 0, v = 0, ret = 0;
            for (int i = 0; i < nums.size(); i ++){
                if (i > u){
                    u = v;
                    v = 0;
                    ret ++;
                }
                v = max(i + nums[i], v);
            }
            return ret;
        }
    };

Log in to reply
 

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