1438. 绝对差不超过限制的最长连续子数组 https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit

862. 和至少为 K 的最短子数组 https://leetcode.cn/problems/shortest-subarray-with-sum-at-least-k

918. 环形子数组的最大和 https://leetcode.cn/problems/maximum-sum-circular-subarray

1696. 跳跃游戏 VI https://leetcode.cn/problems/jump-game-vi

1425. 带限制的子序列和 https://leetcode.cn/problems/constrained-subsequence-sum

前置知识

阅读本文前,你需要先学习:

通用实现

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

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

单调队列 + 滑动窗口

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

基本思路

解法代码

可视化

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

基本思路

解法代码

单调队列 + 环形数组

918. 环形子数组的最大和

基本思路

解法代码

可视化

单调队列 + 动态规划(选学)

1696. 跳跃游戏 VI

基本思路

解法代码

可视化

1425. 带限制的子序列和

基本思路

解法代码

可视化

loading...