leetcode: Jump Game II

문제 조건

• num 배열 원소는 음이 아닌 정수
• 배열의 마지막 요소까지 점프해서 무조건 도달 가능 => 0이 아닌 이상 1칸씩 가면 되니까
• 배열의 각 요소는 해당 위치에서 최대 점프 길이를 나타낸다.

class Solution {
	public int jump(int[] nums) {
		int n = nums.length;
		if (n < 2) {
			return 0;
		}

		int maxPosition = nums[0];
		int maxLength = nums[0];

		int jumps = 1;
		for (int i = 1; i < n; ++i) {
			if (maxLength < i) {
				jumps++;
				maxLength = maxPosition;
			}
			maxPosition = Math.max(maxPosition, nums[i] + i);
		}

		return jumps;
	}
}