LeetCode 239. 滑动窗口最大值（双端队列+单调栈）
LeetCode 239. 滑动窗口最大值（双端队列+单调栈）
Michael阿明
发布于 2021-02-20 11:01:20
发布于 2021-02-20 11:01:20
1. 题目信息
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
示例:
输入: 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提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
进阶：
你能在线性时间复杂度内解决此题吗？
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sliding-window-maximum 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
2.1 暴力法
双重循环查找，O（nk）复杂度
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if(nums.size() == 0)
return {};
int maxnum, i, j;
vector<int> ans;
for(i = 0; i < nums.size()-k+1; ++i)
{
maxnum = nums[i];
for(j = i+1; j < k+i; ++j)
{
if(nums[j] > maxnum)
maxnum = nums[j];
}
ans.push_back(maxnum);
}
return ans;
}
};2.2 双端队列法
将双端队列看做栈，单调递减栈法。
- 在双端队列里保存下标
- 队首保存最大的，队尾保存小的
- 但是注意规则：
- 过了窗口的范围的删除
- 在窗口范围内的k个，每加入一个数nums[i]，只保留前面比它大的，<=nums[i] 的没必要存在，该窗口内它是比较大的
对 {1,3,-1,-3,5,3,6,7}，k = 3
先建立前k个元素的队列：{1}，{1，3}，{1，3，-1}（队列变化过程）（为了方便我用元素值表示）
对后面n-k个元素分别操作：
{3，-1，-3}
{-1，-3， 5}
{-3， 5，3}
{5，3，，6}
{3，6，7}
每次取出队首就是答案。3，3，5，5，6，7
每个元素进出队列，时间复杂度O(n)
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if(nums.size() == 0)
return {};
deque<int> q;
vector<int> ans;
int i;
for(i = 0; i < k; ++i)
{
while(!q.empty() && nums[i] >= nums[q.back()])
{
q.pop_back();// <=nums[i]的前面的存的，无意义，删掉
}
q.push_back(i);
}
ans.push_back(nums[q.front()]);
for(i = k; i < nums.size(); ++i)
{
if(!q.empty() && i-k+1 > q.front())
q.pop_front();//过了窗口了，删除
while(!q.empty() && nums[i] >= nums[q.back()])
{
q.pop_back();
}
q.push_back(i);
ans.push_back(nums[q.front()]);
}
return ans;
}
};《剑指Offer》面试题59 - I. 滑动窗口的最大值
class Solution { //2020.2.21
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if(nums.empty())
return {};
int l = 1, r = 0;
vector<int> ans;
deque<int> q;
while(k--)
{
while(!q.empty() && nums[q.back()] <= nums[r])
{
q.pop_back();
}
q.push_back(r++);
}
ans.push_back(nums[q.front()]);
while(r < nums.size())
{
if(q.front() < l)
q.pop_front();
while(!q.empty() && nums[q.back()] <= nums[r])
{
q.pop_back();
}
q.push_back(r++);
l++;
ans.push_back(nums[q.front()]);
}
return ans;
}
};
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/08/14 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
