1438. 绝对差不超过限制的最长连续子数组 https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit
1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit https://leetcode.com/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
862. Shortest Subarray with Sum at Least K https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k
918. 环形子数组的最大和 https://leetcode.cn/problems/maximum-sum-circular-subarray
918. Maximum Sum Circular Subarray https://leetcode.com/problems/maximum-sum-circular-subarray
1696. 跳跃游戏 VI https://leetcode.cn/problems/jump-game-vi
1696. Jump Game VI https://leetcode.com/problems/jump-game-vi
1425. 带限制的子序列和 https://leetcode.cn/problems/constrained-subsequence-sum
1425. Constrained Subsequence Sum https://leetcode.com/problems/constrained-subsequence-sum
我先提供一个单调队列结构的通用实现,这里涉及 Java 的泛型,E
就代表任意类型,E extends Comparable<E>
的意思是这个类型 E
需要实现 Comparable
接口,即类型 E
是可比较的,比如 Integer, String
这种实现了 compareTo
方法的类型。原因也很好理解,因为你要求队列中元素的最值嘛,所以元素当然得是有大小之分(可比较)的。
我们原先的简陋实现包含了 max
方法的实现,其原理是在底层维护了一个队列 maxq
,维护这个队列中从尾部到头部的元素单调递增。