LI@NG

Leetcode 55 Jump Game II

https://leetcode.com/problems/jump-game-ii/

贪心

1,总是找到每个所在元素的最大可及idx 2,关键点在于,在上述基础之上,如何抽象出和题目结果相关的结果。

在这个例子中,其实就是求,从第一个元素开始,有多少个最大“跨越”,计算每个元素对应的最大跨越,当便利到该最大跨越点时, 即为step应该增加的时候。

注意:遍历的最终点为:nums.length - 1,因为初始的currentMax默认为0,所以当能够遍历的时候,第一次已经加了一步了。

var jump = function(nums) {
	let currentMax = 0;
	let maxNext = 0;
	let steps = 0;
	for (var i = 0; i < nums.length - 1; i++) {
		maxNext = Math.max(maxNext, nums[i] + i);
		if (i === currentMax) {
			steps++;
			currentMax = maxNext;
		}
	}
	return steps;
};