题面：
LeetCode 1696
数据范围：
1 ≤ n u m s . l e n g t h , k ≤ 1 0 5 1 \le nums.length, \ k \le 10^5 1≤nums.length, k≤105
− 1 0 4 ≤ n u m s [ i ] ≤ 1 0 4 -10^4 \le nums \le 10^4 −104≤nums≤104
思绪 & Code
重点： 可以从下标 i i i 跳到 [ i + 1 , m i n ( n − 1 , i + k ) ] [i+1,min(n-1,i+k)] [i+1,min(n−1,i+k)] 区间内的任意一点；得分是所跳到路径的 n u m s nums nums 总和；要求最大得分。
起首天然想到动态规划：设 f [ i ] f f 维护到点 i i i 的最大得分，则 f [ i ] f f 一定是由 j ∈ { 0 , 1 , . . . p ( p < i ) } j\in \{0,1,...p\ (p<i)\} j∈{0,1,...p (p<i)} 中的一个 f [ j ] f[j] f[j] 转移过来的，而且 j + k ≥ i j+k\ge i j+k≥i。直接暴力DP呢，包超的， O ( n 2 ) O(n^2) O(n2)。
但如果只记载前序的最大值 m a x S c o r e maxScore maxScore，却无法判断得到该值的下标 p r e pre pre 是否可以大概跳到当前点 i i i。
接下来就得想优化计谋啦。
1. DP + 最大堆
时间复杂度： O ( n l o g k ) O(nlogk) O(nlogk)
空间复杂度： O ( n ) O(n) O(n)
因为要求最大得分，又是根据前置路径来更新贡献的，以是可以很天然地想到用最大堆去维护前序最大得分，且从下标 0 0 0 开始序次遍历（包管当前点 i i i 的答案是从前序点过来的）。由于有步长限定 k k k，我们必须判断得到最大得分的点 p r e pre pre 是否可以大概跳到当前点 n o w now now，如果其不能跳到，则阐明后续全部点的贡献里都不会有 p r e pre pre 点的贡献。
故可以用 p a i r ( m a x S c o r e , i n d e x ) pair(maxScore, index) 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;
- }
这就不得不提到非常经典的一道题了 LeetCode 239 滑动窗口最大值
时间复杂度： O ( n ) O(n) O(n)
上面提到只存前序最大值而没有其下标是不可的。这边可以想到用滑动窗口去维护 { i − k , i − k + 1 , . . . , i − 1 } \{i-k,i-k+1,...,i-1\} {i−k,i−k+1,...,i−1} 统共 k k k 个 “最大值”。滑动窗口从队首到队尾的索引依次增大，但是对应的值依次递减，即对于队列 { r 1 , r 2 , . . . , r n } \{r_1, r_2, ..., r_n\} {r1,r2,...,rn}，肯定有 d p [ r 1 ] > d p [ r 2 ] > . . . > d p [ r n ] dp[r_1] > dp[r_2] > ... > dp[r_n] dp[r1]>dp[r2]>...>dp[rn]，且 { r 1 < r 2 < r 3 < . . . < r n } \{ r_1 < r_2 < r_3 <... < r_n \} {r1<r2<r3<...<rn}。
遍历时，必要动态维护滑动窗口：
- 当滑动窗口的左界限（最小下标）已经跳不到当前点了，则直接剔除。
- 滑动窗口内只保存贡献（最大值）比当前点还大的元素，其他全部剔除。这是由于如果滑动窗口内小于即是当前点贡献的元素，对后续是肯定没有贡献的。假设 d p [ j ] ≤ d p [ i ] , j ∈ { i − k , i − k + 1 , . . . , i − 1 } dp[j] \le dp\ ,j \in \{ i-k, i-k+1,...,i-1\} dp[j]≤dp ,j∈{i−k,i−k+1,...,i−1}，起首在滑动窗口向右移动的时间 d p [ j ] dp[j] dp[j] 肯定是先被踢出窗口的；其次，当要取到最大值 d p [ i ] = = d p [ j ] dp == dp[j] dp==dp[j] 的时间，由于 i > j i > j i>j， d p [ i ] dp dp 肯定是比 d p [ j ] dp[j] dp[j] 能贡献到更反面的下标的（也就是 i i i 跳的比 j j j 远），以是只保存 i i i 即可。
- 将当前点的贡献和下标一起参加滑动窗口末了
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;
- }
|
发表于 
