[LeetCode 1696] 跳跃游戏 6(Ⅵ)

题面：

LeetCode 1696

数据范围：

$1\le nums.length,k\le 10^5$
$-10^4\le nums[i]\le 10^4$

思路 & Code

重点： 可以从下标 $i$ 跳到 $[i+1,min(n-1,i+k)]$ 区间内的任意一点；得分是所跳到路径的 $nums$ 总和；要求最大得分。

首先自然想到动态规划：设 $f[i]$ 维护到点 $i$ 的最大得分，则 $f[i]$ 必然是由 j ∈ { 0 , 1 , . . . p ( p < i ) } j\in \{0,1,...p\ (p<i)\} j∈{0,1,...p (p<i)} 中的一个 $f[j]$ 转移过来的，并且 $j+k\ge i$。直接暴力DP呢，包超的，$O(n^2)$。
但如果只记录前序的最大值 $maxScore$，却无法判定得到该值的下标 $pre$ 是否能够跳到当前点 $i$。
接下来就得想优化策略啦。

1. DP + 最大堆

时间复杂度： $O(nlogk)$
空间复杂度： $O(n)$

因为要求最大得分，又是根据前置路径来更新贡献的，所以可以很自然地想到用最大堆去维护前序最大得分，且从下标 $0$ 开始顺序遍历（保证当前点 $i$ 的答案是从前序点过来的）。由于有步长限制 $k$，我们必须判断获得最大得分的点 $pre$ 是否能够跳到当前点 $now$，如果其不能跳到，则说明后续所有点的贡献里都不会有 $pre$ 点的贡献。
故可以用 $pair(maxScore,index)$ 来作为最大堆的元素。

Code：

int maxResult(vector<int>& nums, int k) {int n =nums.size();priority_queue<pair<int, int>> q; //优先队列维护最大堆q.push({nums[0], 0});for(int i = 1; i < n; ++i) {//筛选能跳到当前点的最大贡献while(!q.empty() && q.top().second < i - k) q.pop();//更新最大堆q.push({q.top().first + nums[i], i});}while(!q.empty() && q.top().second != n-1) q.pop();return q.top().first;
}

2. DP + 双端队列维护滑动窗口

这就不得不提到非常经典的一道题了 LeetCode 239 滑动窗口最大值

时间复杂度： $O(n)$
上面提到只存前序最大值而没有其下标是不行的。这边可以想到用滑动窗口去维护 { i − k , i − k + 1 , . . . , i − 1 } \{i-k,i-k+1,...,i-1\} {i−k,i−k+1,...,i−1} 总共 $k$ 个 “最大值”。滑动窗口从队首到队尾的索引依次增大，但是对应的值依次递减，即对于队列 { r 1 , r 2 , . . . , r n } \{r_1, r_2, ..., r_n\} {r1​,r2​,...,rn​}，一定有 $dp[r_1]>dp[r_2]>...>dp[r_n]$，且 { r 1 < r 2 < r 3 < . . . < r n } \{ r_1 < r_2 < r_3 <... < r_n \} {r1​<r2​<r3​<...<rn​}。

遍历时，需要动态维护滑动窗口：

1. 当滑动窗口的左边界（最小下标）已经跳不到当前点了，则直接剔除。
2. 滑动窗口内只保留贡献（最大值）比当前点还大的元素，其他全部剔除。这是由于如果滑动窗口内小于等于当前点贡献的元素，对后续是一定没有贡献的。假设 d p [ j ] ≤ d p [ i ] , j ∈ { i − k , i − k + 1 , . . . , i − 1 } dp[j] \le dp[i]\ ,j \in \{ i-k, i-k+1,...,i-1\} dp[j]≤dp[i] ,j∈{i−k,i−k+1,...,i−1}，首先在滑动窗口向右移动的时候 $dp[j]$ 一定是先被踢出窗口的；其次，当要取到最大值 $dp[i]==dp[j]$ 的时候，由于 $i>j$，$dp[i]$ 一定是比 $dp[j]$ 能贡献到更后面的下标的（也就是 $i$ 跳的比 $j$ 远），所以只保留 $i$ 即可。
3. 将当前点的贡献和下标一起加入滑动窗口末尾

Code：

int maxResult(vector<int>& nums, int k) {int n = nums.size(), maxScore = 0;deque<pair<int, int>> dq;dq.emplace_back(nums[0], 0);maxScore = nums[0];for(int i = 1; i < n; ++i) {if(dq.front().second < i - k) dq.pop_front();maxScore = dq.front().first + nums[i];while(!dq.empty() && maxScore >= dq.back().first)dq.pop_back();dq.emplace_back(maxScore, i);}return maxScore;
}