BM45. [滑动窗口的最大值]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM45. 滑动窗口的最大值
根据题意：
要寻找每个滑动窗口的最大值，每次只滑一位
size等于0或者大于数组长度，都返回空值
方法一：暴力法
暴力解法应该是最容易想到的，只需要遍历数组的同时往后遍历每个窗口，找出最大值即可。
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
vector<int> res;
if(size <= num.size() && size != 0) //窗口大于数组长度的时候，返回空
for(int i = 0; i <= num.size() - size; i++){//数组后面要空出窗口大小，避免越界
int max = 0; //寻找每个窗口最大值
for(int j = i; j < i + size; j++){
if(num[j] > max)
max = num[j];
}
res.push_back(max);
}
return res;
}
};
复杂度分析
- 时间复杂度：O(nm)，其中n为数组长度，m为窗口长度，双层for循环
- 空间复杂度：O(1)，没有使用额外的空间，暂存的结果res不算入空间开销
方法二：双向队列法
暴力法重复计算了很多不必要比较。我们都知道，若是一个数字A进入窗口后，若是比窗口内其他数字都大，那么这个数字之前的数字都没用了，因为它们必定会比A早离开窗口，在A离开之前都争不过A，所以A在进入时要依次从后排除掉前面的小值。而当一个窗口最前的数字要离开时，是从前面离开。
因此一个双向队列可以解决这个问题。
具体做法：
维护一个双向队列，用来存储数列的下标，如果即将进入队列的下标的值大于队列后方的值，依次将它们pop掉，再加入。如果某个下标已经过了窗口，则从队列前方将其pop掉。
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size) {
vector<int> res;
if(size <= num.size() && size != 0){//窗口大于数组长度的时候，返回空
deque <int> dq; //双向队列
for(int i =0; i < size; i++){
while(!dq.empty() && num[dq.back()] < num[i]) //去掉比自己先进队列的小于自己的值
dq.pop_back();
dq.push_back(i);
}
for(int i = size; i < num.size(); i++){
res.push_back(num[dq.front()]);
while(!dq.empty() && dq.front() < (i - size + 1))
dq.pop_front(); //弹出窗口移走后的值
while(!dq.empty() && num[dq.back()] < num[i])
dq.pop_back();
dq.push_back(i);
}
res.push_back(num[dq.front()]);
}
return res;
}
};复杂度分析：
- 时间复杂度：O(n)，只遍历一遍数组
- 空间复杂度：O(m)，窗口长度m，双向队列最长时，将窗口填满
