【每日一题】 3-29 滑动窗口
题目链接：
题意：
给 n, k，n 个数字，求所有长度为 k 的区间的最小值和最大值
做法：
单调队列，考虑维护一个单调递增/减的队列，并用滑动窗口的方法使得队列的首尾位置相差<=k，这样每次队首的位置都是长度为 k 的区间的最大/小值
代码：
#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
deque<int>q1, q2;
//q1 单调增 q2 单调减
int a[1000005];
int main()
{
int n, k, t;
sc("%d%d", &n, &k);
vector<int>ans1, ans2;
for (int i = 1; i <= n; i++)
{
sc("%d", &a[i]);
while (!q1.empty() && q1.front() + k <= i)
q1.pop_front();
while (!q1.empty() && a[q1.back()] > a[i])
q1.pop_back();
while (!q2.empty() && q2.front() + k <= i)
q2.pop_front();
while (!q2.empty() && a[q2.back()] < a[i])
q2.pop_back();
q1.push_back(i);
q2.push_back(i);
if (i >= k)
{
ans1.push_back(a[q1.front()]);
ans2.push_back(a[q2.front()]);
}
}
for (int i = 0; i <= n - k; i++)
pr("%d%c", ans1[i], i == n - k ? '\n' : ' ');
for (int i = 0; i <= n - k; i++)
pr("%d%c", ans2[i], i == n - k ? '\n' : ' ');
} 
投递曼伦商贸等公司6个岗位 >
查看8道真题和解析
算法太卷啦