How to solve Leetcode 1340 Jump Game V efficiently?

本文共计666个文字，预计阅读时间需要3分钟。

题目链接：Jump Game V题目大意：给定一个高度数组，每个数字代表一个阶梯的高度。起始位置任意选择，从某个高度（起点）可以跳到另一个高度（终点），但必须满足终点的高度高于起点。要求找到是否能够从一个起点跳到终点，并且路径上任意两个连续的高度差必须大于0。

题目链接：​​Jump Game V​​

题目大意：给定一个高度数组，每个数字代表一个高度，现在有如下规则：起点任选，从某个高度（起点）可以跳到另一个高度（终点），但是要求就是他们之间的距离得不大于d，且他们之间得所有高度值都得小于起始高度（包括终点），求从某个点开始能够访问最多的高度

题目思路：首先我们可以想到一个逆向做法，我们从某个高度到比他低的高度不好做，但是如果我们知道了某一个高度的最多次数，如果某一个高度能够跳到这个高度，那么比较高的高度至少能跳的个数是当前高度+1，那么如果对于所有比当前高度低得高度，跳得个数确定了，那么这个高度实际上能跳得最多个数也就确定了，所以我们得做法其实就是从最低高度到最高得高度，开始计算，找周围比他低得高度，+1之后选最大值，一次类推，即可得到我们想要得答案，具体看代码

时间复杂度&&空间复杂度：O（n^2）&&O（n）

class Solution {
public:
int maxJumps(vector<int>& arr, int d) {
int len = arr.size();
vector<pair<int,int> >vec;
for(int i = 0;i < len;i++){
vec.push_back({arr[i],i});
}
sort(vec.begin(),vec.end());
vector<int>dp(len);
for(int ii = 0;ii < len;ii++){
int i = vec[ii].second;
int now = i-1;
while(now >= 0&&abs(i-now) <= d&&arr[now] < arr[i]){
dp[i] = max(dp[now]+1,dp[i]);
now--;
}
now = i+1;
while(now < len&&abs(i-now) <= d&&arr[now] < arr[i]){
dp[i] = max(dp[now]+1,dp[i]);
now++;
}
}
int maxx = 0;
for(int i = 0;i < len;i++){
maxx = max(maxx,dp[i]);
}
return maxx+1;
}
};