一、题目描述
JZ64滑动窗口的最大值
题目大意：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值
注意审题：窗口大于数组长度的时候，返回空
二、算法1（暴力）
解题思路
根据题目意思，枚举所有的滑动窗口，对于每个窗口，求一下最大值即可，暴力枚举所有滑动窗口的时间复杂度为比较高，一般来说都会超时
代码实现（C++11）
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
vector<int> ans;
int n = num.size();
for(int i = 0; i + size - 1 < n; i++){ // 枚举窗口左边界
int maxval = num[i]; // 记录当前窗口的最大值
int j = i, k = size;
while(k--){
maxval = max(maxval, num[j]);
j++;
}
ans.push_back(maxval); // 将最大值加入结果数组
}
return ans;
}
}; 时间复杂度：O(nm)，n为给定数组的长度，m是滑动窗口的大小
空间复杂度：O(1)
三、算法2（堆）
解题思路
- 暴力法的缺点就是每次求最小值都要把窗口重新遍历一次取出最大值，我们想到堆这一数据结构支持O(logn)查询最大值，故我们可以用一个大根堆来维护滑动窗口中的数
- 每次滑动窗口向右移动时，都会从堆中删除一个数和增加一个数，若是每次都从堆中去找那个需要删除的数，就太耗时间了，影响我们的时间复杂度，因此我们可以在插入元素的同时带上它的下标，当堆顶元素不存在于滑动窗口中时，我们就把它弹出堆，直到堆顶元素属于滑动窗口
- 那么如何判断堆顶元素是否在滑动窗口内呢，我们可以用一个变量维护滑动窗口的左边界，当堆顶元素下标小于左边界时就弹出，可以发现每个元素最多入堆一次出堆一次，故时间复杂度优化到了O(nlogm)
代码实现（C++11）
class Solution {
public:
using PII = pair<int, int>;
vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
vector<int> ans;
priority_queue<PII> que;
int idx = 0;
for(int i = 0; i < num.size(); i++){
que.push({num[i], i}); // 将元素和对应下标入堆
if(i >= size - 1){
while(que.size() && que.top().second < idx){ // 若此时堆顶元素不在窗口内
que.pop(); // 弹出堆顶
}
ans.push_back(que.top().first); // 将在当前窗口的最大元素加入答案数组
++idx;
}
}
return ans;
}
}; 时间复杂度：O(nlogm)，n为给定数组的长度，m为滑动窗口的大小
空间复杂度：O(n)，堆所使用的空间
四、算法3（单调队列）
解题思路
- 单调队列的特点就是从队头到队尾的元素都是单调的，对于本题来说，我们也可以用单调队列来维护滑动窗口的最大值，并且使用单调队列，每次操作的时间复杂度都是线性的，可以更好地优化时间复杂度
- 同样，为了方便排除不在窗口中的元素，我们的单调队列中存放的是下标而不是元素，这样我们可以计算长度是否满足窗口大小，特别地，我们的单调队列不是一般的队列，而是支持尾部进队出队和头部出队的数据结构，因此我们可以使用C++标准库提供的双端队列deque来实现单调递减队列
- 算法流程：首先，若队列为空，则直接入队，不为空，则比较队尾所表示的元素是否小于待入队的元素，若小于，则不断出队，知道队列为空或队尾元素小于等于待入队的元素，这样队头到队尾就形成了一个单调不增的序列；然后我们需要查看一下当前队头元素是否合法，即它的下标是否存在于当前的滑动窗口内，若不存在，则出队。由于滑动窗口每向右移动一次，只会有一个元素出队一个元素入队，因此队头元素不合法的至多只有一个；最后，我们取出队头元素加入答案数组中即可
代码实现（C++11）
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
vector<int> ans;
deque<int> dq; // 双端队列, 里面存的下标
int n = num.size();
for(int i = 0; i < n; i++){
while(!dq.empty() && num[i] > num[dq.back()]){ // 排除无用元素
dq.pop_back();
}
dq.push_back(i); // 将当先元素的下标入队
if(i - dq.front() + 1 > size) dq.pop_front(); // 若队头元素不合法就弹出
if(i >= size - 1) ans.push_back(num[dq.front()]); // 将窗口最大值加入结果数组
}
return ans;
}
}; 时间复杂度：O(n)，n是数组的长度，每个元素只会入队一次出队一次，且每次操作的时间都是线性的
空间复杂度：O(n)，双端队列所使用的空间
京公网安备 11010502036488号