滑动窗口最大值
堆和双向队列
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
这道题有两种解法，一种是使用大顶堆，一种是使用双向队列
方法一：
使用大顶堆，维护一个长度为k的大顶堆，存放的每个元素为一个数对，分别为数值和下标，每次加入新元素，然后把超出窗口的元素删除，怎么算超出窗口呢，也就是下表位于窗口左边界左侧的，如果当前下标为i，那么左边界就是i-k+1。
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
priority_queue<pair<int, int>> q;
for (int i = 0; i < k; ++i) {
q.emplace(nums[i], i);
}
vector<int> ans = {q.top().first};
for (int i = k; i < n; ++i) {
q.emplace(nums[i], i);
while (q.top().second <= i - k) {
q.pop();
}
ans.push_back(q.top().first);
}
return ans;
}
};方法二：
使用一个双向链表，右边入队出队，左边出队排除过期的元素，同时存放的每个元素也是一个数对，分别为数值和下标。对于一个新元素，如果大于队尾，则出队，直到队尾元素小于当前元素，当前元素入队。同时排除掉队头超过窗口边界的元素，下标不符合范围的出队
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
deque<int> q;
for (int i = 0; i < k; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
}
vector<int> ans = {nums[q.front()]};
for (int i = k; i < n; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
while (q.front() <= i - k) {
q.pop_front();
}
ans.push_back(nums[q.front()]);
}
return ans;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-05-04，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
