# Given an array of non-negative integers,
# you are initially positioned at the first index of the array.
#
# Each element in the array represents your maximum jump length at that position.
#
# Your goal is to reach the last index in the minimum number of jumps.
#
# For example:
# Given array A = [2,3,1,1,4]
#
# The minimum number of jumps to reach the last index is 2.
# (Jump 1 step from index 0 to 1, then 3 steps to the last index.)
#
# Note:
# You can assume that you can always reach the last index.
二指针问题,最大覆盖区间。
从左往右扫描,维护一个覆盖区间,每扫过一个元素,就重新计算覆盖区间的边界。
比如,开始时区间[start, end], 遍历A数组的过程中,不断计算A[i]+i最大值(即从i坐标开始最大的覆盖坐标),
并设置这个最大覆盖坐标为新的end边界。
而新的start边界则为原end+1。不断循环,直到 end > n.
class Solution():
def jump(self, x):
if len(x) > 1:
pre, step = [0], 0
while True:
step += 1
left = right = pre[-1] + 1
for p in pre:
if p + x[p] > right:
right = p + x[p]
if right >= len(x)-1:
return step
pre = range(left, right+1)
return 0
if __name__ == "__main__":
assert Solution().jump([2,3,1,1,4]) == 2
assert Solution().jump([3,2,1,0,4]) == 2