[LeetCode] 55 Jump Game

Description

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.

Constraints:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

---

풀이

• 배열의 값만큼 최대로 이동할 수 있는데, 배열의 맨 처음부터 맨 끝까지 도달할 수 있나 확인하는 문제.

• 최대로 이동할 수 있는 범위를 maxJump로 두고 for문을 인덱스의 처음부터 끝까지 돈다.

• 만약 최대로 이동할 수 있는 범위가 현재 인덱스보다 작으면 false를 반환한다.

• maxJump를 현재 인덱스값과 그 인덱스 내의 값을 더한 값과 현재 maxJump의 값과 비교해 큰 값으로 바꾸어 넣는다.

• for문을 다 돌면 true를 반환한다.

---

코드

class Solution {
    public boolean canJump(int[] nums) {
        int maxJump = 0;
        for (int i = 0; i < nums.length; i++) {
            if (maxJump < i) return false;
            maxJump = Math.max(maxJump, nums[i] + i);
        }
        return true;
    }
}