滑动窗口之二(优先队列)

原本滑动窗口的板子用的是数组和双指针模拟，我嫌麻烦还不好懂找了双端队列。但其实还是不太好使，比如今天的这道题就处理起来很麻烦。但是如果用优先队列的话就可以一直保证整个窗口是有序的，只需判断一下是否在窗口内即可。但是！优先队列的时间是会劣于双端队列的，反正这个5e5的数据是过了。下面看题！

题中要找的最小不管是最大的最小还是什么一定是建立在有序的基础上。要想找两个数的差最小，那么这两个数一定是相邻的。第一部就是进行排序。既然题上说了是在固定大小为k的序列中进行查找，那么就是一个滑动窗口的思想。维护固定长度的窗口，每次找当前窗口中最小值然后与之前进行比较。窗口中的最大值一定就是左边界减去右边界，这个没什么变化的。主要就是找最小值。想要一直维护此窗口中差值的最小值不妨先将这个窗口的值全部压进优先队列中，然后每次窗口滑动都将最新的值压进去。在使用最小值(堆顶)的时候需要判断一下此时这个堆顶还在不在窗口中。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define fi first
#define se second
#define pii pair<int, int>
const int N = 1e6+1;
int a[N];
void solve()
{priority_queue<pii, vector<pii>, greater<pii>> q;//前面窗口中相邻差(min值)，后边存下标int n,k;cin >> n >> k;for(int i=1; i<=n; i++) cin >> a[i];sort(a+1,a+1+n);int ans = 1e18;for(int i=2; i<=k; i++) q.push({a[i]-a[i-1],i});//先将第一个窗口压进去for(int i=k; i<=n; i++)//将第一个窗口重复压进去，为了判断是否刚好第一个窗口就是最小值{q.push({a[i]-a[i-1],i});while(!q.empty()&&i-k>=q.top().se)//如果此时堆顶已经不在窗口中就要弹出去q.pop();ans=min(ans,q.top().fi*(a[i]-a[i-k+1]));//每次对它进行更新}cout << ans;
}
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t=1;
//	cin >> t;while(t--) solve();
}