发布日期: 2025-06-14

文章字数: 6.9k

【练习】单调队列的通用实现及经典习题

通用实现

我先提供一个单调队列结构的通用实现，这里涉及 Java 的泛型，E 就代表任意类型，E extends Comparable<E> 的意思是这个类型 E 需要实现 Comparable 接口，即类型 E 是可比较的，比如 Integer, String 这种实现了 compareTo 方法的类型。原因也很好理解，因为你要求队列中元素的最值嘛，所以元素当然得是有大小之分（可比较）的。

我们原先的简陋实现包含了 max 方法的实现，其原理是在底层维护了一个队列 maxq，维护这个队列中从尾部到头部的元素单调递增。

那么实现 min 方法也是类似的，可以在底层再维护一个 minq 队列，维护队列中元素从尾部到头部的元素单调递减，这样头部第一个元素就是所有元素中的最小值了。

当然，由于 push 方法在添加元素的同时还可能会删除元素，所以 maxq 和 minq 中都没有保存所有元素。如果想实现标准的 pop 方法以及 size 方法，我们还得再额外维护一个标准队列 q，这个 q 存储所有存在于队列中的元素，不维护单调性。

综上，可以得到 MonotonicQueue 的通用实现，具体逻辑看注释：

from collections import deque
from typing import TypeVar, Generic

E = TypeVar('E')

# 单调队列的实现，可以高效维护最大值和最小值
class MonotonicQueue(Generic[E]):
    def __init__(self):
        # 常规队列，存储所有元素
        self.q = deque()
        # 元素降序排列的单调队列，头部是最大值
        self.maxq = deque()
        # 元素升序排列的单调队列，头部是最小值
        self.minq = deque()

    def push(self, elem: E):
        # 维护常规队列，直接在队尾插入元素
        self.q.append(elem)

        # 维护 maxq，将小于 elem 的元素全部删除
        while self.maxq and self.maxq[-1] < elem:
            self.maxq.pop()
        self.maxq.append(elem)

        # 维护 minq，将大于 elem 的元素全部删除
        while self.minq and self.minq[-1] > elem:
            self.minq.pop()
        self.minq.append(elem)

    def max(self) -> E:
        # maxq 的头部是最大元素
        return self.maxq[0]

    def min(self) -> E:
        # minq 的头部是最大元素
        return self.minq[0]

    def pop(self) -> E:
        # 从标准队列头部弹出需要删除的元素
        deleteVal = self.q.popleft()
        assert deleteVal is not None

        # 由于 push 的时候会删除元素，deleteVal 可能已经被删掉了
        if deleteVal == self.maxq[0]:
            self.maxq.popleft()
        if deleteVal == self.minq[0]:
            self.minq.popleft()
        return deleteVal

    def size(self) -> int:
        # 标准队列的大小即是当前队列的大小
        return len(self.q)

    def isEmpty(self) -> bool:
        return not self.q

需要注意的是，这个通用实现内部维护了三个队列，且涉及到 Java 的泛型，所以在刷题平台上执行的效率不会高，如果你追求效率的话，可以根据具体的题目简化单调队列的实现，从而提升效率。下面看几道单调队列的经典应用。

单调队列 + 滑动窗口

单调队列可以和滑动窗口算法结合，在窗口滑动的过程中快速计算窗口内部的最值。

1438. 绝对差不超过限制的最长连续子数组

1438. 绝对差不超过限制的最长连续子数组 | 力扣 | LeetCode | 🟠

给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。

如果不存在满足条件的子数组，则返回 0 。

示例 1：

输入：nums = [8,2,4,7], limit = 4
输出：2 
解释：所有子数组如下：
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4. 
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4. 
因此，满足题意的最长子数组的长度为 2 。

示例 2：

输入：nums = [10,1,2,4,7,2], limit = 5
输出：4 
解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。

示例 3：

输入：nums = [4,2,2,2,4,4,2,2], limit = 0
输出：3

提示：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= limit <= 10^9

题目来源：力扣 1438. 绝对差不超过限制的最长连续子数组。

基本思路

很明显这道题需要用到前文讲的滑动窗口技巧核心框架详解：

当窗口内绝对值之差不超过 limit 时扩大窗口，当新加入窗口的元素使得绝对值之差超过 limit 时开始收缩窗口，窗口的最大宽度即最长子数组的长度。

但有个问题，当窗口进新元素时，我可以更新窗口中的最大值和最小值，但当窗口收缩时，如何更新最大值和最小值呢？难道要遍历一遍窗口中的所有元素吗？这就用到单调队列结构了，这里需要一个通用的 MonotonicQueue 类，用来高效判断窗口中的最大值和最小值。

PS：MonotonicQueue 的通用实现见单调队列设计与实现

详细题解：

【练习】单调队列的通用实现及经典习题

解法代码

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        left = 0
        right = 0
        windowSize = 0
        res = 0
        window = MonotonicQueue()
        # 滑动窗口模板
        while right < len(nums):
            # 扩大窗口，更新窗口最值
            window.push(nums[right])
            right += 1
            windowSize += 1
            while window.max() - window.min() > limit:
                # 缩小窗口，更新窗口最值
                window.pop()
                left += 1
                windowSize -= 1
            # 在窗口收缩判断完之后才更新答案
            res = max(res, windowSize)
        return res

# 下面给出的是单调队列的通用实现，运行速度可能较慢，你可以自行简化提升速度
# 单调队列的详细解析见
# https://labuladong.online/algo/problem-set/monotonic-queue/
class MonotonicQueue:
    def __init__(self):
        # 常规队列，存储所有元素
        self.q = collections.deque()
        # 元素降序排列的单调队列，头部是最大值
        self.maxq = collections.deque()
        # 元素升序排列的单调队列，头部是最小值
        self.minq = collections.deque()

    def push(self, elem: int):
        # 维护常规队列，直接在队尾插入元素
        self.q.append(elem)

        # 维护 maxq，将小于 elem 的元素全部删除
        while self.maxq and self.maxq[-1] < elem:
            self.maxq.pop()
        self.maxq.append(elem)

        # 维护 minq，将大于 elem 的元素全部删除
        while self.minq and self.minq[-1] > elem:
            self.minq.pop()
        self.minq.append(elem)

    def max(self) -> int:
        # maxq 的头部是最大元素
        return self.maxq[0]

    def min(self) -> int:
        # minq 的头部是最大元素
        return self.minq[0]

    def pop(self) -> int:
        # 从标准队列头部弹出需要删除的元素
        deleteVal = self.q.popleft()

        # 由于 push 的时候会删除元素，deleteVal 可能已经被删掉了
        if deleteVal == self.maxq[0]:
            self.maxq.popleft()
        if deleteVal == self.minq[0]:
            self.minq.popleft()
        return deleteVal

    def size(self) -> int:
        # 标准队列的大小即是当前队列的大小
        return len(self.q)

    def isEmpty(self) -> bool:
        return not self.q

可视化

算法可视化面板

862. 和至少为 K 的最短子数组

862. 和至少为 K 的最短子数组 | 力扣 | LeetCode | 🔴

给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。

子数组 是数组中连续的一部分。

示例 1：

输入：nums = [1], k = 1
输出：1

示例 2：

输入：nums = [1,2], k = 4
输出：-1

示例 3：

输入：nums = [2,-1,2], k = 3
输出：3

提示：

1 <= nums.length <= 10⁵
-10⁵ <= nums[i] <= 10⁵
1 <= k <= 10⁹

题目来源：力扣 862. 和至少为 K 的最短子数组。

基本思路

这题的难度是比较大的，难点在于同时结合了滑动窗口算法、前缀和技巧和单调队列几个知识点，建议你先理解这三篇文章的要义，否则看不懂这题的解法。

首先，想要快速记录子数组的和，需要前缀和技巧预计算一个 preSum 数组，然后在这个 preSum 数组上施展滑动窗口算法寻找一个差值大于等于 k 且宽度最小的「窗口」，这个窗口的大小就是题目想要的结果。

这里面还有个问题，当滑动窗口扩大时，新进入窗口的元素 preSum[right] 需要知道窗口中最小的那个元素是多少，和最小的那个元素相减才能得到尽可能大的子数组和。

如何快速判断窗口中的最值？这就需要单调队列结构出马了，直接看解法代码吧。

PS：MonotonicQueue 的通用实现见单调队列设计与实现

详细题解：

【练习】单调队列的通用实现及经典习题

解法代码

class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        # 看题目的数据范围，前缀和数组中元素可能非常大，所以用 long 类型
        preSum = [0] * (n + 1)
        preSum[0] = 0
        # 计算 nums 的前缀和数组
        for i in range(1, n + 1):
            preSum[i] = preSum[i - 1] + nums[i - 1]
        # 单调队列结构辅助滑动窗口算法
        window = MonotonicQueue()
        right = 0
        left = 0
        length = float('inf')
        # 开始执行滑动窗口算法框架
        while right < len(preSum):
            # 扩大窗口，元素入队
            window.push(preSum[right])
            right += 1
            # 若新进入窗口的元素和窗口中的最小值之差大于等于 k，
            # 说明得到了符合条件的子数组，缩小窗口，使子数组长度尽可能小
            while right < len(preSum) and not window.isEmpty() and preSum[right] - window.min() >= k:
                # 更新答案
                length = min(length, right - left)
                # 缩小窗口
                window.pop()
                left += 1
        return -1 if length == float('inf') else length

# 下面给出的是单调队列的通用实现，运行速度可能较慢，你可以自行简化提升速度
# 单调队列的详细解析见
# https://labuladong.online/algo/problem-set/monotonic-queue/
class MonotonicQueue:
    def __init__(self):
        # 常规队列，存储所有元素
        self.q = collections.deque()
        # 元素降序排列的单调队列，头部是最大值
        self.maxq = collections.deque()
        # 元素升序排列的单调队列，头部是最小值
        self.minq = collections.deque()

    def push(self, elem):
        # 维护常规队列，直接在队尾插入元素
        self.q.append(elem)

        # 维护 maxq，将小于 elem 的元素全部删除
        while self.maxq and self.maxq[-1] < elem:
            self.maxq.pop()
        self.maxq.append(elem)

        # 维护 minq，将大于 elem 的元素全部删除
        while self.minq and self.minq[-1] > elem:
            self.minq.pop()
        self.minq.append(elem)

    def max(self):
        # maxq 的头部是最大元素
        return self.maxq[0]

    def min(self):
        # minq 的头部是最大元素
        return self.minq[0]

    def pop(self):
        # 从标准队列头部弹出需要删除的元素
        deleteVal = self.q.popleft()

        # 由于 push 的时候会删除元素，deleteVal 可能已经被删掉了
        if deleteVal == self.maxq[0]:
            self.maxq.popleft()
        if deleteVal == self.minq[0]:
            self.minq.popleft()
        return deleteVal

    def size(self):
        # 标准队列的大小即是当前队列的大小
        return len(self.q)

    def isEmpty(self):
        return not self.q

类似题目：

单调队列 + 环形数组

单调队列还可以在环形数组的场景下排上用场。之前单调栈原理中讲了只要把数组的长度 n 加倍就可以模拟环形数组，但如果让你在环形数组中计算子数组的元素和就需要单调队列辅助了，因为你要保证子数组的长度不能超过 n。

918. 环形子数组的最大和

918. 环形子数组的最大和 | 力扣 | LeetCode | 🟠

给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。

环形数组 意味着数组的末端将会与开头相连呈环状。形式上， nums[i] 的下一个元素是 nums[(i + 1) % n] ， nums[i] 的前一个元素是 nums[(i - 1 + n) % n] 。

子数组 最多只能包含固定缓冲区 nums 中的每个元素一次。形式上，对于子数组 nums[i], nums[i + 1], ..., nums[j] ，不存在 i <= k1, k2 <= j 其中 k1 % n == k2 % n 。

示例 1：

输入：nums = [1,-2,3,-2]
输出：3
解释：从子数组 [3] 得到最大和 3

示例 2：

输入：nums = [5,-3,5]
输出：10
解释：从子数组 [5,5] 得到最大和 5 + 5 = 10

示例 3：

输入：nums = [3,-2,2,-3]
输出：3
解释：从子数组 [3] 和 [3,-2,2] 都可以得到最大和 3

提示：

n == nums.length
1 <= n <= 3 * 10⁴
-3 * 10⁴ <= nums[i] <= 3 * 10⁴

题目来源：力扣 918. 环形子数组的最大和。

基本思路

诚然，这道题有很巧妙的方法，你可以搜索一下「Kadane 算法」来解决这道题。不过为了举一反三地运用我之前讲过的算法技巧，我就结合单调队列结构和前文前缀和技巧写一个更通用的解法。

首先，这道题和 53. 最大子序和非常类似，区别在于本题的数组是环形的，所以上一题的动态规划思路和前缀和思路都不能直接套用过来。不过前文单调栈结构详解中讲过处理环形数组的方法，其实就是把原数组大小扩大一倍，这样就能模拟出环形的效果了。

那么本题也可以把 nums 数组扩大一倍，计算前缀和数组 preSum，借助一个定长为 nums.length 的单调队列来计算环形数组中的最大子数组和。具体实现直接看代码吧。

PS：MonotonicQueue 的通用实现见单调队列设计与实现

详细题解：

【练习】单调队列的通用实现及经典习题

解法代码

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        n = len(nums)
        # 模拟环状的 nums 数组
        preSum = [0] * (2 * n + 1)
        preSum[0] = 0
        # 计算环状 nums 的前缀和
        for i in range(1, len(preSum)):
            preSum[i] = preSum[i - 1] + nums[(i - 1) % n]
        # 记录答案
        maxSum = float('-inf')
        # 维护一个滑动窗口，以便根据窗口中的最小值计算最大子数组和
        window = MonotonicQueue()
        window.push(0)
        for i in range(1, len(preSum)):
            maxSum = max(maxSum, preSum[i] - window.min())
            # 维护窗口的大小为 nums 数组的大小
            if window.size() == n:
                window.pop()
            window.push(preSum[i])
        return maxSum

# 下面给出的是单调队列的通用实现，运行速度可能较慢，你可以自行简化提升速度
# 单调队列的详细解析见
# https://labuladong.online/algo/problem-set/monotonic-queue/
class MonotonicQueue:
    # 常规队列，存储所有元素
    def __init__(self):
        self.q = collections.deque()
        # 元素降序排列的单调队列，头部是最大值
        self.maxq = collections.deque()
        # 元素升序排列的单调队列，头部是最小值
        self.minq = collections.deque()

    def push(self, elem):
        # 维护常规队列，直接在队尾插入元素
        self.q.append(elem)

        # 维护 maxq，将小于 elem 的元素全部删除
        while self.maxq and self.maxq[-1] < elem:
            self.maxq.pop()
        self.maxq.append(elem)

        # 维护 minq，将大于 elem 的元素全部删除
        while self.minq and self.minq[-1] > elem:
            self.minq.pop()
        self.minq.append(elem)

    def max(self):
        # maxq 的头部是最大元素
        return self.maxq[0]

    def min(self):
        # minq 的头部是最大元素
        return self.minq[0]

    def pop(self):
        # 从标准队列头部弹出需要删除的元素
        deleteVal = self.q.popleft()

        # 由于 push 的时候会删除元素，deleteVal 可能已经被删掉了
        if deleteVal == self.maxq[0]:
            self.maxq.popleft()
        if deleteVal == self.minq[0]:
            self.minq.popleft()
        return deleteVal

    def size(self):
        # 标准队列的大小即是当前队列的大小
        return len(self.q)

    def isEmpty(self):
        return not self.q

可视化

算法可视化面板

单调队列 + 动态规划（选学）

动态规划很多时候会用到嵌套 for 循环计算最值，如果是计算一个窗口中的最值，可以利用单调队列结构维护最值，从而消除一层 for 循环，降低时间复杂度。

1696. 跳跃游戏 VI

1696. 跳跃游戏 VI | 力扣 | LeetCode | 🟠

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [1,-5,-20,4,-1,3,-6,-3], k = 2
输出：0

提示：

1 <= nums.length, k <= 10⁵
-10⁴ <= nums[i] <= 10⁴

题目来源：力扣 1696. 跳跃游戏 VI。

基本思路

这题和 1425. 带限制的子序列和非常像：

1425 题是让你求最大子序列和，子序列中每两个元素之间的间隔不能超过 k；这道题其实也是让你求元素间隔不超过 k 的最大子序列和，只不过又多了些限制，即子序列的第一个元素必须是 nums[0]，最后一个元素必须是 nums[-1]。

你可以想办法复用第 1425 题的解法，不过我这里按照标准的动态规划解题框架来逐步优化，最后通过单调队列结构中给出的单调队列通用实现来优化动态规划解法的效率。

需要注意的是，本题使用标准的动态规划解法也会超时，这并不是动态规划的锅，而是本题给的数据规模太大，需要更先进的数据结构（单调队列）来优化状态转移的效率。

PS：MonotonicQueue 的通用实现见单调队列设计与实现

详细题解：

【练习】单调队列的通用实现及经典习题

解法代码

# 第一步，暴力递归解法（超时）
class Solution1:
    def maxResult(self, nums: List[int], k: int) -> int:
        n = len(nums)
        return self.dp(nums, n - 1, k)

    # 定义：到达 nums[p] 所能获得的最大分数是 dp(nums, p)
    # 能跳到 nums[p]，必然是从 nums[p-k..p-1] 中的某个位置跳来的
    # 故状态转移方程为：dp[p] = max(nums[p-k..p-1]) + nums[p]
    def dp(self, nums: List[int], p: int, k: int) -> int:
        if p == 0:
            return nums[0]
        if p < 0:
            return float('-inf')
        # 实现状态转移方程
        res = float('-inf')
        for i in range(1, k + 1):
            res = max(res, self.dp(nums, p - i, k))
        res += nums[p]
        return res

# 第二步，带备忘录的递归解法（超时）
class Solution2:
    # 备忘录
    def __init__(self):
        self.memo = []

    def maxResult(self, nums: List[int], k: int) -> int:
        n = len(nums)
        self.memo = [float('-inf')] * n
        # 备忘录初始化为最小值
        return self.dp(nums, n - 1, k)

    # 定义：到达 nums[p] 所能获得的最大分数是 dp(nums, p)
    def dp(self, nums: List[int], p: int, k: int) -> int:
        if p == 0:
            return nums[0]
        if p < 0:
            return float('-inf')
        # 查备忘录，避免冗余计算
        if self.memo[p] != float('-inf'):
            return self.memo[p]
        # 实现状态转移方程，结果存入备忘录
        for i in range(1, k + 1):
            self.memo[p] = max(self.memo[p], self.dp(nums, p - i, k))
        self.memo[p] += nums[p]
        return self.memo[p]

# 第三步，自顶向下的递归改为自底向上的迭代解法（超时）
class Solution3:
    def maxResult(self, nums: List[int], k: int) -> int:
        n = len(nums)
        # 定义：到达 nums[p] 的最大分数为 dp[p]
        dp = [float('-inf')] * n
        # dp 数组初始化为最小值
        dp[0] = nums[0]
        # 状态转移
        for p in range(1, n):
            for i in range(1, k + 1):
                if p - i < 0:
                    continue
                dp[p] = max(dp[p], dp[p - i])
            dp[p] += nums[p]
        return dp[n - 1]

# 第四步，利用单调队列结构消除内层循环（通过）
class Solution:
    def maxResult(self, nums: List[int], k: int) -> int:
        n = len(nums)
        window = MonotonicQueue()
        # 定义：到达 nums[p] 的最大分数为 dp[p]
        dp = [float('-inf')] * n
        # dp 数组初始化为最小值
        dp[0] = nums[0]
        window.push(dp[0])
        # 状态转移
        for p in range(1, n):
            dp[p] = window.max() + nums[p]
            # 维护窗口装着 dp[p-1..p-k]
            if window.size() == k:
                window.pop()
            window.push(dp[p])
        return dp[n - 1]

# 下面给出的是单调队列的通用实现，运行速度可能较慢，你可以自行简化提升速度
# 单调队列的详细解析见
# https://labuladong.online/algo/problem-set/monotonic-queue/
class MonotonicQueue:
    # 常规队列，存储所有元素
    def __init__(self):
        self.q = collections.deque()
        # 元素降序排列的单调队列，头部是最大值
        self.maxq = collections.deque()
        # 元素升序排列的单调队列，头部是最小值
        self.minq = collections.deque()

    def push(self, elem: int):
        # 维护常规队列，直接在队尾插入元素
        self.q.append(elem)

        # 维护 maxq，将小于 elem 的元素全部删除
        while self.maxq and self.maxq[-1] < elem:
            self.maxq.pop()
        self.maxq.append(elem)

        # 维护 minq，将大于 elem 的元素全部删除
        while self.minq and self.minq[-1] > elem:
            self.minq.pop()
        self.minq.append(elem)

    def max(self) -> int:
        # maxq 的头部是最大元素
        return self.maxq[0]

    def min(self) -> int:
        # minq 的头部是最大元素
        return self.minq[0]

    def pop(self):
        # 从标准队列头部弹出需要删除的元素
        deleteVal = self.q.popleft()

        # 由于 push 的时候会删除元素，deleteVal 可能已经被删掉了
        if deleteVal == self.maxq[0]:
            self.maxq.popleft()
        if deleteVal == self.minq[0]:
            self.minq.popleft()

    def size(self) -> int:
        # 标准队列的大小即是当前队列的大小
        return len(self.q)

    def isEmpty(self) -> bool:
        return not self.q

可视化

算法可视化面板

1425. 带限制的子序列和

1425. 带限制的子序列和 | 力扣 | LeetCode | 🔴

给你一个整数数组 nums 和一个整数 k ，请你返回非空子序列元素和的最大值，子序列需要满足：子序列中每两个相邻的整数 nums[i] 和 nums[j] ，它们在原数组中的下标 i 和 j 满足 i < j 且 j - i <= k 。

数组的子序列定义为：将数组中的若干个数字删除（可以删除 0 个数字），剩下的数字按照原本的顺序排布。

示例 1：

输入：nums = [10,2,-10,5,20], k = 2
输出：37
解释：子序列为 [10, 2, 5, 20] 。

示例 2：

输入：nums = [-1,-2,-3], k = 1
输出：-1
解释：子序列必须是非空的，所以我们选择最大的数字。

示例 3：

输入：nums = [10,-2,-10,-5,20], k = 2
输出：23
解释：子序列为 [10, -2, -5, 20] 。

提示：

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

题目来源：力扣 1425. 带限制的子序列和。

基本思路

如果你看过后文最长递增子序列问题详解，那么这道题的思路应该是很简单的：

设计一个 dp 数组，dp[i] 表示以 nums[i] 为结尾的最大子序列之和，然后题目要求的答案就是 max(dp[..])。

由于题目说两个序列之间的间隔不能超过 k，所以 dp[i] 的值就可以根据 dp[i-k..i-1] 的值推导出来，那么状态转移逻辑就是：

for (int i = 1; i < n; i++) {
    int maxVal = 0;
    for (int j = 1; j <= k; j++) {
        maxVal = Math.max(maxVal, dp[i - j]);
    }
    dp[i] = maxVal + nums[i];
}

想到这一步其实已经可以写出动态规划解法代码了，但由于测试数据的规模较大，这个 O(KN) 的算法会超时。

我们注意到内层的 for 循环实际上就是在计算 dp[i-k..i-1] 的最大值，随着 i 的增加，dp[i-k..i-1] 就像一个滑动前进的窗口，这个场景不需要傻乎乎用 for 循环遍历求最值，前文讲到的单调队列可以高效实现这个过程，将整个算法的复杂度降低到 O(N)。

我将给出经过单调队列优化的解法代码和未经优化的解法代码，注意单调队列在其中起到的作用。

PS：MonotonicQueue 的通用实现见单调队列设计与实现

详细题解：

【练习】单调队列的通用实现及经典习题

解法代码

# 经过单调队列优化的动态规划解法
class Solution:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        # 定义：dp[i] 表示以 nums[i] 结尾的子序列的最大和
        dp = [0] * n
        dp[0] = nums[0]
        # 单调队列辅助计算 dp[i-k..i-1] 的最大值
        window = MonotonicQueue()
        window.push(dp[0])

        for i in range(1, n):
            # 状态转移方程
            dp[i] = max(nums[i], window.max() + nums[i])
            # 维护滑动窗口的大小为 k
            if window.size() == k:
                window.pop()
            window.push(dp[i])
        
        # dp 数组中的最大值就是结果
        res = float('-inf')
        for i in range(n):
            res = max(res, dp[i])
        return res

# 下面给出的是单调队列的通用实现，运行速度可能较慢，你可以自行简化提升速度
# 单调队列的详细解析见
# https://labuladong.online/algo/problem-set/monotonic-queue/
class MonotonicQueue:
    # 常规队列，存储所有元素
    def __init__(self):
        self.q = collections.deque()
        # 元素降序排列的单调队列，头部是最大值
        self.maxq = collections.deque()
        # 元素升序排列的单调队列，头部是最小值
        self.minq = collections.deque()

    def push(self, elem):
        # 维护常规队列，直接在队尾插入元素
        self.q.append(elem)

        # 维护 maxq，将小于 elem 的元素全部删除
        while self.maxq and self.maxq[-1] < elem:
            self.maxq.pop()
        self.maxq.append(elem)

        # 维护 minq，将大于 elem 的元素全部删除
        while self.minq and self.minq[-1] > elem:
            self.minq.pop()
        self.minq.append(elem)

    def max(self):
        # maxq 的头部是最大元素
        return self.maxq[0]

    def min(self):
        # minq 的头部是最大元素
        return self.minq[0]

    def pop(self):
        # 从标准队列头部弹出需要删除的元素
        deleteVal = self.q.popleft()

        # 由于 push 的时候会删除元素，deleteVal 可能已经被删掉了
        if deleteVal == self.maxq[0]:
            self.maxq.popleft()
        if deleteVal == self.minq[0]:
            self.minq.popleft()
        return deleteVal

    def size(self):
        # 标准队列的大小即是当前队列的大小
        return len(self.q)

    def isEmpty(self):
        return not self.q

# 未经优化的动态规划解法，超时
class Solution2:
    def constrainedSubsetSum(self, nums: List[int], k: int) -> int:
        n = len(nums)
        # 定义：dp[i] 表示以 nums[i] 结尾的子序列的最大和
        dp = [0] * n
        # base case，以 nums[0] 结尾的子序列只有它本身
        dp[0] = nums[0]

        # 状态转移方程
        for i in range(1, n):
            maxVal = 0
            for j in range(1, k+1):
                if i - j < 0:
                    continue
                maxVal = max(maxVal, dp[i - j])
            # dp[i] 的值可以根据 dp[i-k..i-1] 的最大值推导出来
            dp[i] = maxVal + nums[i]

        # dp 数组中的最大值就是结果
        res = float('-inf')
        for i in range(n):
            res = max(res, dp[i])
        return res