Thought:
start: the starting index, inclusive.
end: the ending index, exclusive.
max: the max index that could be reached.
steps: the steps used.
We start from [start, end) to reach out, update the [start, end) to [end, max + 1)
if end = A.length(Or max >= A.length - 1), return the result.
Code:
public class Solution {
public int jump(int[] A) {
int start = 0, end = 1, max = 0, steps = 0;
while (end < A.length) {
steps++;
for (int i = start; i < end; i++) {
if (A[i] + i >= A.length - 1) return steps;
max = Math.max(A[i] + i, max);
}
start = end;
end = max + 1;
}
return steps;
}
}
No comments:
Post a Comment