给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
1. 暴力遍历(超时)
暴力法
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
vector<int> res;
for(int i=0;i<n-k+1;i++){
int mx = INT_MIN;
for(int j=i;j<i+k;j++)
mx = max(mx,nums[j]);
res.push_back(mx);
}
return res;
}
};
2. 红黑树
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
vector<int> res;
map<int,int> m;
for(int i=0;i<k-1;i++)
m[nums[i]]++;
for(int i=k-1;i<n;i++){
if(i!=k-1){
m[nums[i-k]]--;
if(m[nums[i-k]]==0) m.erase(nums[i-k]);
}
m[nums[i]]++;
auto it = m.rbegin();
res.push_back(it->first);
}
return res;
}
};
3. 线段树
套模板
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
vector<int> res;
vector<TreeNode> tree(n*4);//线段树
build(nums,tree,0,0,n-1);
for(int i=0;i<n-k+1;i++){
int val = query(tree,0,i,i+k-1);
res.push_back(val);
}
return res;
}
struct TreeNode {
int left; // 节点区间左边界
int right; // 节点区间右边界
int value; // 节点存储的信息，这里以区间最值为例
};
void build(vector<int>& arr, vector<TreeNode>& tree, int index, int left, int right) {
tree[index].left = left;
tree[index].right = right;
// 叶子节点，存储输入数组的元素值
if (left == right) {
tree[index].value = arr[left];
return;
}
// 非叶子节点，递归构建左子树和右子树
int mid = (left + right) / 2;
build(arr, tree, index * 2 + 1, left, mid);//递归建左树
build(arr, tree, index * 2 + 2, mid + 1, right);//递归建右树
// 更新当前节点的信息，这里以区间最值为例
tree[index].value = max(tree[index * 2 + 1].value, tree[index * 2 + 2].value);
}
int query(vector<TreeNode>& tree, int index, int left, int right) {
// 当前节点区间与查询区间完全重合，直接返回节点存储的信息
if (tree[index].left == left && tree[index].right == right)
return tree[index].value;
else {
// 否则，根据查询区间与节点区间的关系递归查询左子树或右子树
int mid = (tree[index].left + tree[index].right) / 2;
// 查询区间完全位于左子树
if (right <= mid)
return query(tree, index * 2 + 1, left, right);
// 查询区间完全位于右子树
else if (left > mid)
return query(tree, index * 2 + 2, left, right);
// 查询区间同时位于左子树和右子树，取两者查询结果的最值
else
return max(query(tree, index * 2 + 1, left, mid), query(tree, index * 2 + 2, mid + 1, right));
}
}
};
4. 优先队列（大根堆）
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-1; ++i)
q.push({nums[i],i});//值和索引对
vector<int> res;
for (int i = k-1; i < n; i++) {
q.push({nums[i], i});
while (q.top().second <= i - k)
q.pop();
res.push_back(q.top().first);
}
return res;
}
};
5. 双端队列（单调栈操作最优解）
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
vector<int> res;
deque<int> q;//双端队列存储下标，从后端进行类似单调栈的操作
for (int i = 0; i < k-1; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) //当前数把小数挤出
q.pop_back();
q.push_back(i);//留在最前头的一定是最大的
}
for (int i = k-1; 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();
res.push_back(nums[q.front()]);
}
return res;
}
};