leetcode/cpp/JumpGame2.cc at master · speedfirst/leetcode

22 lines (20 loc) · 599 Bytes

namespace JumpGame2 {
    class Solution {
    public:
        int jump(int A[], int n) {
            int step = 0;
            int lastCanReach = 0; // mark the last reachable pos
            int maxCanReach = 0;
            int i = 0;
            while (i < n) {
                if (i > lastCanReach) { // reach the edge of current range
                    step++;
                    lastCanReach = maxCanReach;
                if (i + A[i] > maxCanReach) maxCanReach = i + A[i];
            return step;

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

FilesExpand file tree

JumpGame2.cc

Latest commit

History

JumpGame2.cc

File metadata and controls