力扣hot100 跳跃游戏 II 贪心 思维

Problem: 45. 跳跃游戏 II

思路

👨‍🏫 参考

• 每次在上次能跳到的范围（end）内选择一个能跳的最远的位置（也就是能跳到max_far位置的点）作为下次的起跳点 ！

Code

⏰ 时间复杂度: $O(n)$
🌎 空间复杂度: $O(1)$

class Solution {
	public int jump(int[] nums)
	{
		int steps = 0;
		int n = nums.length;
		int end = 0; // 上次跳跃可达范围右边界（下次的最右起跳点）
		int maxPos = 0;// 目前能跳到的最远位置
		for (int i = 0; i < n - 1; i++)
		{
			maxPos = Math.max(maxPos, nums[i] + i);// 这里贪的是 (nums[i]+i)
//			   到达上次跳跃能到达的右边界了
			if (i == end)
			{
				end = maxPos; // 目前能跳到的最远位置变成了下次起跳位置的有边界
				steps++;// 进入下一次跳跃
			}
		}
		return steps;
	}
}