AI summary
type
status
date
slug
summary
category
tags
icon
password
我们原先的简陋实现包含了 max 方法的实现，其原理是在底层维护了一个队列 maxq，维护这个队列中从尾部到头部的元素单调递增。
那么实现 min 方法也是类似的，可以在底层再维护一个 minq 队列，维护队列中元素从尾部到头部的元素单调递减，这样头部第一个元素就是所有元素中的最小值了。

单调队列+滑动窗口

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

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

给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。
如果不存在满足条件的子数组，则返回 0 。
很明显要用到滑动窗口，当窗口内绝对值之差不超过 limit 时扩大窗口，当新加入窗口的元素使得绝对值之差超过 limit 时开始收缩窗口，窗口的最大宽度即最长子数组的长度。
但有个问题，当窗口进新元素时，我可以更新窗口中的最大值和最小值，但当窗口收缩时，如何更新最大值和最小值呢？难道要遍历一遍窗口中的所有元素吗？这就用到单调队列结构了，使用前文写的 MonotonicQueue 类，用来高效判断窗口中的最大值和最小值。

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

给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。
子数组 是数组中 连续 的一部分。
提示：
  • 1 <= nums.length <= 10^5
  • -10^5 <= nums[i] <= 10^5
  • 1 <= k <= 10^9
这题的难度是比较大的，难点在于同时结合了 滑动窗口算法、前缀和技巧 和 单调队列 几个知识点，建议你先理解这三篇文章的要义，否则看不懂这题的解法。
首先，想要快速记录子数组的和，需要 前缀和技巧 预计算一个 preSum 数组，然后在这个 preSum 数组上施展 滑动窗口算法 寻找一个差值大于等于 k 且宽度最小的「窗口」，这个窗口的大小就是题目想要的结果。
这里面还有个问题，当滑动窗口扩大时，新进入窗口的元素 preSum[right] 需要知道窗口中最小的那个元素是多少，和最小的那个元素相减才能得到尽可能大的子数组和。
如何快速判断窗口中的最值？这就需要单调队列结构出马了，直接看解法代码吧。
如果写滑动窗口有点卡手，建议回去复习一下 滑动窗口算法核心代码模板。

单调队列+环形数组

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

918. 环形子数组的最大和

给定一个长度为 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 。
诚然，这道题有很巧妙的方法，你可以搜索一下「Kadane 算法」(动态规划) 来解决这道题。不过为了举一反三地运用我之前讲过的算法技巧，我就结合 单调队列结构 和前文 前缀和技巧 写一个更通用的解法。
和上面那道题类似，区别在于本题的数组是环形的。不过处理环形数组的方法，其实就是把原数组大小扩大一倍，这样就能模拟出环形的效果了。
那么本题也可以把 nums 数组扩大一倍，计算前缀和数组 preSum，使用一个固定大小为 nums.length 的滑动窗口，窗口内最大值-最小值得到答案。具体实现直接看代码吧。
好好体会一下，为什么能固定大小为 n。注意在窗口扩张过程中要维护答案。

单调队列+动态规划

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

1696. 跳跃游戏 VI

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。
一开始你在下标 0 处。每一步，你最多可以往前跳 k 步，但你不能跳出数组的边界。也就是说，你可以从下标 i 跳到 [i + 1， min(n - 1, i + k)] 包含 两个端点的任意位置。
你的目标是到达数组最后一个位置（下标为 n - 1 ），你的 得分 为经过的所有数字之和。
请你返回你能得到的 最大得分 。
这题和 1425. 带限制的子序列和 非常像：
1425 题是让你求最大子序列和，子序列中每两个元素之间的间隔不能超过 k；这道题其实也是让你求元素间隔不超过 k 的最大子序列和，只不过又多了些限制，即子序列的第一个元素必须是 nums[0]，最后一个元素必须是 nums[-1]。
需要注意的是，本题使用标准的动态规划解法也会超时，这并不是动态规划的锅，而是本题给的数据规模太大，需要更先进的数据结构（单调队列）来优化状态转移的效率。
下面是一般的动态规划代码，会超时：

1425. 带限制的子序列和

给你一个整数数组 nums 和一个整数 k ，请你返回 非空 子序列元素和的最大值，子序列需要满足：子序列中每两个 相邻 的整数 nums[i] 和 nums[j] ，它们在原数组中的下标 i 和 j 满足 i < j 且 j - i <= k 。
数组的子序列定义为：将数组中的若干个数字删除（可以删除 0 个数字），剩下的数字按照原本的顺序排布。
和上面一样，直接看代码吧。