力扣239.滑动窗口最大值问题
题目描述
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
进阶：
你能在线性时间复杂度内解决此题吗？
示例
思路
-
解法一、暴力解法
随着窗口的移动，每移动依次窗口，遍历一遍窗口返回最大值
时间复杂度为（n-k）*k，最后评测超时 -
解法二、单调队列
窗口的移动，类似于队列两端一端弹出一个元素，另一端进入一个元素
但是，每次需要返回队列中最大的那个元素，这个元素显然不一定在队列的两端
所以，我们想到是有序队列，可能是优先队列（另一个解法，后面再补充）
因此，我们这里采用单调队列
单调队列基于双端队列dequeue, 需要我们自个定义push\pop\front等函数操作
此题为单调递减队列单调队列的相关操作
-
push(int value)操作
pop（）函数对应---窗口右移一位，对最右端新元素的操作
当队列为空时，直接将value从队尾加入队列；
当队列不为空时，需要持续将队尾与value比较，
若队尾元素小于value，需要把队尾元素弹出，直到大于value，再将value入列
-
pop(int value)操作
push（）函数对应---窗口右移一位，对最左端旧元素value的操作
通过push函数，我们知道单调队列的头部为最大的元素
对于pop（value）中的参数value对应的元素：可能不一定再单调队列中，可能在push操作的时候就已经被弹出了，此时不用弹出元素；
也有可能value对应的元素就是最大元素，此时需弹出最大元素。
-
front（）操作
front()函数对应---返回当前窗口的最大值
-
代码实现
class Solution
{
private:
class Queue_tool // 自定义一个队列，pop(value),push(value) 对应窗口移动,front() 对应返回窗口最大值
{
public:
deque<int> que;
void pop(int value)
{
if (!que.empty() && value == que.front())
{
que.pop_front();
}
}
void push(int value)
{
while (!que.empty() && value > que.back())
{
que.pop_back();
}
que.push_back(value);
}
int front()
{
return que.front();
}
};
public:
vector<int> maxSlidingWindow(vector<int> &nums, int k)
{
Queue_tool que;
vector<int> result;
for (int i = 0; i < k; i++)
{
que.push(nums[i]);
}
result.push_back(que.front());
for (int i = k; i < nums.size(); i++)
{
que.pop(nums[i - k]);
que.push(nums[i]);
result.push_back(que.front());
}
return result;
}
};