题目描述
贪心题,难以发现中间的证明思路和一些点
算法1
(贪心) $O(n)$
- 这道题最重要的点是在于分析出他每个跳跃步数是单调的,而且是分段单调,可以看yxc的证明
- 之后就可以边枚举边维护上一段最右能跳到哪儿,每次跳到最右了r,且没有到终点就必须跳一步,之后r更新为下一个区间最右跳到哪儿
C++ 代码
class Solution {
public:
int jump(vector<int>& nums) {
int l = 0, r = 0, last_r = 0; // r是下一段段最右能到哪儿,last_r 是当前区间最右点
int res = 0;
for (int i = 0; i < nums.size() - 1; i++) {
r = max(r, i + nums[i]);
if (i == last_r) {
res++;
last_r = r;
}
}
return res;
}
};