题解 | #java 几步能从头走到尾#

人无远虑，必有近忧，如果只顾着当前利益，不为自己的将来做打算的话，结果往往不如人意

这道题也是一个道理，如果我们只是想着这一步能走的最远距离是多少，那么我们肯定是达不到预期的效果的，所以我们在走每一步的时候要想着下一步，简单说，就是考虑下两步能达到的最远距离，来决定下一步该到达的位置，最远的，不一定是最好的。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最少需要跳跃几次能跳到末尾
     * @param n int整型 数组A的长度
     * @param A int整型一维数组 数组A
     * @return int整型
     */

    public int Jump (int n, int[] A) {
        // write code here
        int res = 0;// 结果
        int pos = 0;// 当前位置

        int step, max, maxStep;

        while (true) {
            if (pos + A[pos] >= n - 1) {
                return res + 1; // 如果当前位置的可达区域比n - 1还要大， 则加一返回结果
            }
            step = 1; // 遍历可达位置用
            max = A[pos + step] + 1; // 接下来两步走的最远距离
            maxStep = 1; // 假如走一步能使其在走下一步之后达到最远距离
            while (step <= A[pos]) { // 遍历， 刷新maxStep
                if (A[pos + step] + step >= max) { // 如果走这一步加上下一步走的比max更大，刷新max和maxstep
                    max = A[pos + step] + step;
                    maxStep = step;
                }
                step++;
            }
            pos += maxStep;
            res++;
        }
    }
}