本文最后更新于 704 天前,其中的信息可能已经有所发展或是发生改变。
Origional link
思想:
- 贪心;
- 对于当前所处的位置
i
,当 i + nums[i] >= n - 1
时可以直接返回结果;
- 否则,从
j = i
遍历到 j = i + nums[i]
,设下一步的位置为 res
,以 res
能到达的最远位置为 idx
;
- 显然,
j + nums[j]
即为下一步可以到达的最远位置 idx
;
- 则只需找到
j + nums[j]
的最大值,并用 res
维护下一步的坐标 j
即可。
代码:
| class Solution { |
| public int jump(int[] nums) { |
| int ans = 0, n = nums.length; |
| if(n <= 1) return 0; |
| for(int i = 0; i < n; i ++){ |
| int res = 0, idx = 0; |
| if(i + nums[i] >= n - 1) return ans + 1; |
| for(int j = i + 1; j <= i + nums[i]; j ++){ |
| if(j + nums[j] >= idx){ |
| idx = j + nums[j]; |
| res = j; |
| } |
| } |
| i = res - 1; ans ++; |
| } |
| return ans; |
| } |
| } |