題目鏈接：點擊查看

題目分析：給出 $n$ 個數，定義滑動窗口的貢獻是其中最大值與最小值的乘積，現在問對于長度分別為 $[1,n]$ 的滑動窗口，貢獻之和分別是多少

題目分析：考慮暴力解法，是直接 $RMQ$ 預處理一下，然后 $O(n^2)$ 去模擬整個過程

正難則反，考慮正這去枚舉區間不行，那么我們是否可以通過枚舉每個數字，從而計算每個數字對區間的貢獻呢

根據滑動窗口的定義，不難發現在每個長度下的滑動窗口，對于每個位置來說，都有可能作為一次窗口的起點或終點（如果越界的話有時候某些位置是無法滿足條件的）

按照官方題解的思路，就是是去枚舉 $n$ 個位置作為滑動窗口的終點，我們記為 $r$，然后利用單調棧去維護一下最值，這樣就可以將區間 $[1,r]$ 劃分成數個連續的區間，滿足所有的區間拼接起來就是總區間 $[1,r]$。對于劃分后的某段區間 $[x,y]$ 來說，滿足 $i\in [x,y]$，區間 $[i,r]$ 的最大值和最小值是相同的。這樣滑動窗口的長度屬于 $[r?y+1,r?x+1]$ 的貢獻加上相應的乘積即可。區間更新最后統一查詢，這里我選擇使用的是差分數組

最后就是復雜度該如何證明呢，由于本題 $a_i$ 的上限是 $100$，所以單調棧中維護的元素最多不可能超過 $100$ 個，由于同時需要維護兩個單調棧分別維護最大值和最小值，所以拼接起來劃分的區間最多也是 $100+100=200$ 個，也就是說每次最多會將區間 $[1,r]$ 劃分成 $200$ 個子區間，利用差分暴力更新即可，時間復雜度 $O(n?max(a_i)?2)$

代碼：

// Problem: 牛牛的滑動窗口 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/7604/D // Memory Limit: 524288 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; int a[N],ans[N],mitp,mxtp; struct Node {int val,pos; }mi[N],mx[N]; void add(int l,int r,int val) {ans[l]+=val;ans[r+1]-=val; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;read(n);for(int i=1;i<=n;i++) {read(a[i]);}for(int i=1;i<=n;i++) {while(mitp&&mi[mitp].val>=a[i]) {mitp--;}while(mxtp&&mx[mxtp].val<=a[i]) {mxtp--;}int mmax=a[i],mmin=a[i],pos=i,tp1=mitp,tp2=mxtp;while(tp1||tp2) {if(tp1&&tp2) {if(mi[tp1].pos>=mx[tp2].pos) {add(i-pos+1,i-mi[tp1].pos,mmin*mmax);mmin=mi[tp1].val;pos=mi[tp1].pos;tp1--;} else {add(i-pos+1,i-mx[tp2].pos,mmin*mmax);mmax=mx[tp2].val;pos=mx[tp2].pos;tp2--;}} else if(tp1) {add(i-pos+1,i-mi[tp1].pos,mmin*mmax);mmin=mi[tp1].val;pos=mi[tp1].pos;tp1--;} else if(tp2) {add(i-pos+1,i-mx[tp2].pos,mmin*mmax);mmax=mx[tp2].val;pos=mx[tp2].pos;tp2--;}}add(i-pos+1,i,mmin*mmax);mx[++mxtp]={a[i],i};mi[++mitp]={a[i],i};}for(int i=1;i<=n;i++) {ans[i]+=ans[i-1];printf("%d ",ans[i]);}return 0; }

總結

以上是生活随笔為你收集整理的牛客 - 牛牛的滑动窗口(单调栈+思维+差分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。