Leetcode 2024-02-05 题目分享

经典DP和延迟删除问题

跳跃游戏 VI

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, i + k)] 包含两个端点的任意位置。

你的目标是到达数组最后一个位置（下标为 n - 1 ），你的得分为经过的所有数字之和。

请你返回你能得到的 最大得分 。

示例 1：

1
2
3

输入：nums = [1,-1,-2,4,-7,3], k = 2
输出：7
解释：你可以选择子序列 [1,-1,4,3] （上面加粗的数字），和为 7 。

示例 2：

1
2
3

输入：nums = [10,-5,-2,4,0,3], k = 3
输出：17
解释：你可以选择子序列 [10,4,3] （上面加粗数字），和为 17 。

提示：

1 <= nums.length, k <= 10^5
-10^4 <= nums[i] <= 10^4

思路

题意很简单，一眼DP问题。
写出原始DP转移方程：设dp[i]表示跳跃到第i个位置时最大得分。

则根据第i个位置可以由第i-1，i-2，…i-k个位置跳跃而来有以下转移方程

dp[i] =max(dp[i-1],dp[i-2],...,dp[i-k]+nums[i])
很明显，接下来的问题就是要动态维护前k个dp最大值。
但动态维护需要删除操作，去除那些不在前k的值。此时我们可以使用延迟删除方法。

这样可以保证每个值最多只会有一次push和一次pop操作。

代码

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
        typedef pair<int, int> pii;
        int n = nums.size(), ans = 0;
        priority_queue<pii> pq;
        for (int i = 0;i < n;i++){
            int cur = nums[i];
            // 延迟删除 
            // 判断当前队列里最大值是不是在前k个位置中
            while (pq.size() && pq.top().second < i - k){
                pq.pop();
            }
            if (pq.size()) cur += pq.top().first;
            pq.push({cur, i});
            ans = cur;
        }
        return ans;
    }
};

复杂度分析

时间：O(n * log n)。
空间：O(n)。