单调队列详解[C/C++]

单调队列

前言

一、滑动窗口

1、引例

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。其中：

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• 1 <= k <= nums.length

朴素做法

以我们朴素的思维，我们会想到维护这个窗口，每向右滑动一次，就计算一次最值，计算最值时间复杂度为O(k)，滑动结束的时间复杂度为O(n)，总的时间复杂度为O(N * k)，而根据这道题1e5的数据量，显然会超时

ST表/线段树解决区间最值

这其实是一个经典的区间最值问题，我们可以用稀疏(ST，Sparse Table)表来求解，时间复杂度为O(n logk)，也可以用线段树来求解区间最值，时间复杂度也是O(n logk)

设计数据结构

本文着重介绍的是一种O(n)的算法，它基于数据结构——单调队列。

对于滑动窗口向右滑动一次其实只出队了一个元素，进队了一个元素，不过相差了两个元素而已。

如果我们有一种容器，该容器能够支持：

1、O(1)时间获取容器中最大元素

2、O(1)时间删除元素

3、O(1)时间插入元素

那么我们只要不断地移动滑动窗口，每移动一次，删除一个元素，插入另一个元素，并且记录下最大值，那么，每一次滑动，只要三步0(1)的操作。总共n次滑动，只要O(n)的时间就可以解决这个问题。

这种容器就是我们本文的主角——单调队列。

二、单调队列

1、 定义

单调队列是一-个限制只能队尾插入，但是可以两端删除的双端队列。单调队列存储的元素值，是从队首到队尾弹调性的(要么单调递增,要么单调递减)。
对于求解最大值的问题，则需要维护-个单调递减的队列。

如图所际，⑨为原先的队首元素，执行队首删除(出队)操作以后，⑥成为新的队元素;而在队尾执行插入④这个元素的时候，为为保持单调性,要将①②依次从队尾删除;当队尾执行插入②这个元素的时候，满足单调性。

2、 询问

于单调队列是单调递减的，所以队首元愫最大，直接0(1)获取队首元素。

如图所际，head 指向队首元素，直接获取，于这是一个单调递减队列，所以得到的，就是最大值。

3、 删除

删除分为队首删除和队尾删除。
队首删除即直接队首元素出队，0(1) 即可完成操作。如图所际:

队尾删除一般是配合队尾插入进行的。我们接着往下看。

4、 插入

在进行队尾插入的时候，我们往往需要明白一个重要的点，就是需要保证它单调递减的性质，所以如果队元素≤插入元素，则当前的队元素要执行删除操作的(也就是文提到的队尾删除)，直到满足队朊素>插入元素,才能真正执行插入操作。
这样才能保证，执行队尾插入后,单调队列仍然是单调递减的。插入过程，虽然伴随着元素的删除，但是每个元素至多被插入一次和删除-次,所以均摊时间复杂度还是O(1)的。

如图所示，在队尾执行插入④这个元索的时候，为了保持单调性，需要将①②依次从队尾删除;当队尾执行插入②这个元素的时候，满足单调性，所以直接执行插入操作。

5、性质

1)保序性
于单调队列执行插入的时候，-定是从队尾进行插入，所以单调队列中的数据,从队首到队尾的顺序，一定是和原序列严格保序的;
2)下标存储
为了让单调队列的数据足够干净,在单调队列中, 一般存储原序列的下标即啊，不需要存储原序列的值，根据保序性,存储的下标一定是单调递增的;
3)单调性
单调队列中的元素是原序列的下标，对应到原序列时,根据求解问题的不同,当需要求最大值时，它是单调递减的;当需要求最小值时，它是单调递增的;

三、单调队列的应用

1、最值问题

1)问题描述
继续回到文提到的滑动窗口中的最大值问题。

[例题1]给定一个长度为n(n≤100000)整数数组Ai,有一个大小为k(k≤100000)的滑动窗口从数组的最左侧移动到数组的最右侧。只能看到在滑动窗口内的k个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

2)思路分析
我们要实现的，就是把原序列A中的元素逐个执行单调队列的插入操作。当插入的原序列的下标为i时,期望是单调队列中的元素从队首到队尾都在原序列的区间(i-k, i]范围内(也就是以i为右端点，长度为k的区间内)，且对应到原序列的值单调递减，这样每次插入完毕，就可以在
0(1)的时间内,从队首获取到最大值(即区间(i-k, ij] 内的最大值)。
为什么是单调递减?而不是单调递增?
对于每个要插入的下标i,队尾的元素为原序列的下标j,则根据保序性,一定能够满足 j <i,如果对应到原序列中,满足Aj≤Ai,那么Aj不会蚍Ai更优,原因是:对于区间(i-k, i]来说，Ai一定在区间内，而Aj则未必，也就是说下标j没必要存储到单调队列中。于是对于单调队列中的存储的元素i1 <i2<…<in需要满足: Ai1 > Ai2 > … > Ain,即维护一个单调递减的队列。
实际执行过程中，每次插入后，队尾元素减去队首元素必须小于等于k-1, -旦超过k-1,就
要从队首不断出队了。

3)代码实现

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> pq;
        vector<int> ret;
        int i;
        for(i = 0 ; i < k ; i++)
        {
            while(!pq.empty() && nums[pq.back()] <= nums[i])
            pq.pop_back();
            pq.push_back(i);
        }
        ret.push_back(nums[pq.front()]);
        for(i = k ; i < n ; i++)
        {
            while(!pq.empty() && nums[pq.back()] <= nums[i])
            pq.pop_back();
            pq.push_back(i);
            while(!pq.empty() && i - pq.front() + 1 > k)
            pq.pop_front();
            ret.push_back(nums[pq.front()]);
        }
        return ret;
    }
};

2、DP优化

1)问题描述

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

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

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

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

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

2)思路分析
比较容易想到的是动态规划，假设跳到位置i的最大值是dp[i]，那么-定是从[i-k, i-1]中的某个位置跳过来的，可以得到状态转移方程如下: dp[i] = ai + max(dp[-1], … dp[i-k])
但是这一步的问题在于，数组长度为n时，每次状态转移的时间为O(k),所以整个算法的时间复杂度为O(n k)。所以我们要想办法max(dp[i-1], … dp[i-k])这步操作化为O(1)。
维护一个单调递减的队列,这样就能通过O(1)的时间找到从队首找到最大值。单调队列始终保持dp[…]的元素在队列中是单调递减的。并且时刻保证，当前元素插入单调队列之后，队首元素x，满足i - x <= k

class Solution {
public:
    int maxResult(vector<int>& nums, int k) {
       int n = nums.size();
       vector<int> dp(n);
       dp[0] = nums[0];
       deque<int> q;
       q.push_back(0);
       for(int i = 1 ; i < n ; i++)
       {
           while(!q.empty() && i - q.front() > k)
           q.pop_front();
           dp[i] = dp[q.front()] + nums[i];
           while(!q.empty() && dp[q.back()] <= dp[i])
           q.pop_back();
           q.push_back(i);
       }
       return dp[n - 1];
    }
};