4.4 单调队列

4.4.1 LeetCode239——滑动窗口的最大值★★★

【问题描述】 给定一个整数数组nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。用户只可以看到滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。请返回滑动窗口中的最大值。

例如，nums=[1，3，-1，-3，5，3，6，7]， k =3时的答案为[3，3，5，5，6，7]。

【限制】 1≤nums.length≤10 ⁵ ，-10 ⁴ ≤nums[ i ]≤10 ⁴ ，1≤ k ≤nums.length。

【解题思路】 用单调递减队保存滑动窗口中的最大元素 。定义一个双端队列dq（大头队），用ans记录该滑动窗口内元素的最大值。用 i 从0开始遍历nums：

（1）若队列dq为空，将 i 从队尾进队。

（2）若队列dq不为空，将小于nums[ i ]的队尾元素从队尾出队，直到队列为空或者队尾不小于nums[ i ]为止，再将 i 从队尾进队。

对于当前滑动窗口，如果队列的队头元素的位置“过期”，也就是队头下标小于该滑动窗口最左端的位置（ i - k +1），将队头元素从队头出队。当 i ≥ k -1时形成一个滑动窗口，将队头元素作为滑动窗口的最大值添加到ans中。最后返回ans。对应的算法如下。

C++：

提交运行：

Python：

提交运行：

4.4.2 LeetCode1438——绝对差不超过限制的最长连续子数组★★

【问题描述】 给定一个整数数组nums和一个表示限制的整数limit，请返回最长连续子数组的长度，该子数组中任意两个元素之间的绝对差必须小于或者等于limit。如果不存在满足条件的子数组，则返回0。

例如，nums=[8，2，4，7]，limit=4，子数组[2，4]的最大绝对差|2-4|=2≤4，答案为2。

【限制】 1≤nums.length≤10 ⁵ ，1≤nums[ i ]≤10 ⁹ ，0≤limit≤10 ⁹ 。

【解题思路】 用两个单调队列保存区间中的最大元素和最小元素 。用[low，high]作为滑动窗口（初始为[0，0]），ans表示答案（初始为0），设置大头队maxdq和小头队mindq。在遍历nums的一个窗口时始终维护maxdq中的队头元素为该窗口中的最大元素，mindq中的队头元素为该窗口中的最小元素。当maxdq的队头元素减去mindq的队头元素大于limit时，该窗口不再是有效窗口，应该将窗口的左边框向后移动一个位置，在移动之前若该窗口的最大元素为nums[low]，则将其从maxdq的队头出队，若该窗口的最小元素为nums[low]，则将其从mindq的队头出队，然后继续判断，直到当前窗口为有效窗口为止。

对于每个有效窗口[low，high]，其长度为high-low+1，将最大长度存放在ans中，然后递增high继续，直到high= n 为止。

例如，nums=[8，2，4，7]，limit=4，ans=0，high=0，maxdq=[]，mindq=[]，求解过程如下。

（1）high=0，将nums[0]=8分别进maxdq和mindq队列，maxdq=[8]，mindq=[8]。[0，0]是有效区间，其长度为1，得到ans=1。

（2）high=1，maxdq的操作：nums[1]=2不大于队头元素8，所以8不出队，将nums[1]进队，maxdq=[8，2]。mindq的操作：nums[1]=2小于队头元素8，将8从队头出队，再将nums[1]进队，mindq=[2]。此时maxdq和mindq的队头元素差超过limit，且maxdq队头元素等于nums[0]，则将8从maxdq队头出队，maxdq=[2]，mindq不变，low增1，得到low=1。[1，1]是有效区间，其长度为1，得到ans=1。

（3）high=2，maxdq和mindq操作后，maxdq=[4]，mindq=[2，4]。[1，2]是有效区间，其长度为2，得到ans=2。

（4）high=3，maxdq和mindq操作后，maxdq=[7]，mindq=[2，4，7]，修改为low=2。[2，3]是有效区间，其长度为2，得到ans=2。

答案为2。

4.4.3 LCR184——设计自助结算系统★★

【问题描述】 请设计一个自助结账系统，该系统需要通过一个队列来模拟顾客通过购物车的结算过程，需要实现的功能有：

（1）get_max（）：获取结算商品中的最高价格，如果队列为空，则返回-1。

（2）add（val）：将价格为val的商品加入待结算商品队列的尾部。

（3）remove（）：移除第一个待结算的商品价格，如果队列为空，则返回-1。

注意，为保证该系统运转高效性，以上函数的均摊时间复杂度均为 O （1）。

例如，输入[＂Checkout＂，＂add＂，＂add＂，＂get_max＂，＂remove＂，＂get_max＂][[]，[4]，[7]，[]，[]，[]]，输出的结果为[null，null，null，7，4，7]。

提示：1≤get_max，add，remove的总操作数≤10 000，1≤val≤10 ^{^} 5。

【解题思路】 用单调递减队保存整个队列中的最大元素 。 设置一个普通队列 qu 和维护队列最大值的单调队列 dq， 后者采用双端队列 deque 实现 。

（1）get_max（）： 若 qu 空时返回 -1， 否则直接返回 dq 的队头元素 （ 即为队列中的最大值 ）。

（2）add（val）： 先将 val 进入 qu 队 ， 若 dq 中队尾元素小于 val， 将 dq 队尾元素出队 ， 直到 dq 为空或者队尾元素不小于 val 为止 ， 再将 val 从队尾进入 dq。

（3）remove（）： 若 qu 空时返回 -1， 否则取 qu 的队头元素 x ， 若 dq 的队头元素 （ 当前队列中的最大值 ） 等于 x ， 则同时将 x 从 dq 的队头出队 ， 最后返回 x 。

对应 Checkout 类如下 。

C++：

提交运行：

Python：

提交运行： DHUiMlvtJfhl/7FsfDwiJBymW8DjAmNeJ3VRgmnVR/eTsQ5g4kzTOGk/d2oi/R+d