239. 滑动窗口最大值
题目链接
状态：暴力ok
文档：programmercarl.com
1、（暴力算法）思路：
一共有两层循环，外层循环（N）迭代变量，内层循环（K）每一个窗口，并计算这个窗口的最大值。时间复杂度O(N*K)。
代码：
class Solution {
public:
//暴力
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
//短路条件
int size = nums.size();
//存放结果的数组
vector<int> result;
if(size == 0) return result;
for(int i=0;i<=size-k;i++)
{
//最大值
int max = nums[i];
for(int j=i;j<=i+k-1;j++)
{
//计算每个窗口内的最大值
if(nums[j] > max) max = nums[j];
}
result.push_back(max);
}
return result;
}
};
2、（单调队列）思路：
可以看到，每移动一次窗口，原理上都是把左边的元素pop出去，右边新加一个元素进来。
但是有时候并不需要去pop那个被窗口抛弃的元素，因为在某些元素push进来之前，我们会先对队列进行一个判断大小的操作：
- 如果要push进来的元素比队列入口处的元素大，那么就要把这些元素一 一pop掉，（因此之后可能就不用去pop那个被窗口抛弃的元素，因为已经被pop掉了）这样就保证了队列是一个单调递减的队列。
- 之后若要pop出口处的元素，那么下一个元素一定是下一个窗口的最大值。
- 并且，若pop的元素==队列出口的元素，那么说明pop的元素是这个窗口的最大值。
代码：
class Solution {
private:
class MyQueue{
public:
//定义一个队列que，实现单调队列
deque<int> que;
// 每次弹出的时候，比较当前要弹出的数值是否等于队列出口元素的数值，如果相等则弹出。
// 如果不相等的话说明此时要pop的数比出口数小，在出口数push前该数就已经被pop了。
// 同时pop之前判断队列当前是否为空。
void pop(int value){
if(!que.empty() && value == que.front())
que.pop_front();
}
// 如果push的数值大于入口元素的数值，那么就将队列后端的数值弹出，直到push的数值小于等于队列入口元素的数值为止。
// 这样就保持了队列里的数值是单调从大到小的了。
void push(int value){
while(!que.empty() && value > que.back())
que.pop_back(); // 把小的数都pop
//小的数pop完再push新的大的数
que.push_back(value);
}
// 返回窗口最大值
int getWindowMax(){
return que.front();
}
};
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
MyQueue que;
vector<int> result;
//先把前k个数放到que中
for(int i=0;i<k;i++){
que.push(nums[i]); // 已经保证现在的队列是一个单调队列了
}
// 此时已经产生了一个窗口的最大值，记录下来
result.push_back(que.getWindowMax());
// 窗口移动时，左边的元素被移除，右边的元素会新加进来
for(int j=k;j<nums.size();j++){
// 左边的元素移除掉
que.pop(nums[j-k]);
// 右边的元素加进来
que.push(nums[j]);
// 形成了新的窗口，返回窗口的最大值
result.push_back(que.getWindowMax());
}
return result;
}
};
注意：
在push函数中，判断要加进来的value是否＞队列入口处的值时，因为这个比较次数是不确定的，所以不能用if判断，而要用while判断才行。