单调队列优化DP，LeetCode1696. 跳跃游戏 VI

一、题目

1、题目描述

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

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

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

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

2、接口描述

​

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {

    }
};

3、原题链接

1696. 跳跃游戏 VI

二、解题报告

1、思路分析

很经典的单调队列优化dp模型，令f[i]等于跳到下标i处的最大得分

那么f[i] = max(f[j])(i - j <= k) + nums[i]

如果按照O(n)状态转移的线性dp来做，那么需要O(N^2)的时间复杂度，我们发现优化只能从状态转移上入手

我们要找到i之前的最大f，线性枚举的话，要O(N)，这就涉及到区间最值的快速查询了

我们可以选择：

树状数组，O(logn）查询

线段树，O(logn）查询

当然有点杀鸡用牛刀了，有一种更方便的方法：单调队列

维护从对头到队尾单调递减的单调队列就能获取前缀最小值了

单调队列本质是滑动窗口，总体时间复杂度为O(N)，均摊时间复杂度为O(1)，故算法时间复杂度为O(N)

2、复杂度

时间复杂度： O(N) 空间复杂度：O(N)

3、代码详解

​

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