【算法日记】力扣239 滑动窗口最大值
题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
思路
首先，最好想的是暴力解决，但是暴力方法的时间复杂度是O(n * k)，当n或者k增加，乘积将会非常大，非常容易TLE。不妨换一种方法，我们使用一个队列，这个队列比较特殊，在队首的是这个区间内的最大值，有了这个队列，这个题就会非常好解决，但是STL中没有这样的队列，我们只能手搓一下这个队列。手搓之前，我们先来构思一下：
- 这个类需要有队列的基本功能
- pop出来的时候，只有当参数等于队列前元素时弹出队列前元素
- push进去的时候，当参数大于队尾时，pop队尾所有元素，该元素push队列（保证队尾元素是即将最大的元素）
- front函数就很简单了，调用就告诉你这个区间的最大值
基于上面的美好愿景，我们使用deque来实现，也就是我们的这个队列是基于deque魔改
deque<int> que;
deque是一个双向队列
下面是这个类的源码：
class MyQueue {
public:
deque<int> que;
// 函数说明：当参数等于队列前元素时弹出队列前元素
void pop(int value) {
if (!que.empty() && value == que.front()) {
que.pop_front();
}
}
// 函数说明：当参数大于队尾时，pop队尾所有元素，该元素push队列（保证队尾元素是即将最大的元素）
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) {
MyQueue que;
vector<int> res;
// 先放入前k个元素
for (int i = 0; i < k; i++) {
que.push(nums[i]);
}
res.push_back(que.front());
for (int i = k; i < nums.size(); i++) {
que.pop(nums[i-k]);
que.push(nums[i]);
res.push_back(que.front());
}
return res;
}
};
口头来描述一下主函数的过程，我们说我们现在实现的函数是调用front函数就会告诉你窗口最大值那么怎么判断这个队首元素该弹出了呢，我们可以来滑动窗口，当窗口末尾的元素和这个队列的首项相同时弹出，那么队列的队首就会变为下一个元素，我们称这个元素是即将要变为最大的元素，那么这个元素怎么来的呢？也是通过滑动窗口时，进来的元素和队尾打擂台，比他大，队尾就走，赢家就进入，通过这样，我们就可以保持队尾的元素，也就是即将变大的元素总是最大的，名副其实
程序源码
class Solution {
private:
class MyQueue {
public:
deque<int> que;
// 函数说明：当参数等于队列前元素时弹出队列前元素
void pop(int value) {
if (!que.empty() && value == que.front()) {
que.pop_front();
}
}
// 函数说明：当参数大于队尾时，pop队尾所有元素，该元素push队列（保证队尾元素是即将最大的元素）
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) {
MyQueue que;
vector<int> res;
// 先放入前k个元素
for (int i = 0; i < k; i++) {
que.push(nums[i]);
}
res.push_back(que.front());
for (int i = k; i < nums.size(); i++) {
que.pop(nums[i-k]);
que.push(nums[i]);
res.push_back(que.front());
}
return res;
}
};
原文地址：https://blog.csdn.net/Coniary/article/details/143029473
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！