45. Jump Game II

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

• T: $O(N)$
• S: $O(1)$