题目描述
给你一个整数数组 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] <= 104
1 <= 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;
}
};