題目鏈接：點擊查看

題目大意：給出一段長度為n的序列，現(xiàn)在給出一個m和一個k，必須滿足一段連續(xù)區(qū)間內(nèi)的最大值與最小值的差值大于等于m并且小于等于k，問滿足條件的連續(xù)區(qū)間的最大長度

題目分析：一開始看到連續(xù)區(qū)間就想到了尺取，用尺取寫了一發(fā)直接WA掉了，后來想了一下，這個題目和尺取沒什么關(guān)系，因為區(qū)間內(nèi)的最大值和最小值并不會因為兩個指針的移動而成線性的改變，他們的變化是無規(guī)律的，所以更不能二分了（或許可以二分，但絕對不是簡單的二分），然后就不知所措了，去網(wǎng)上看了大佬的題解，發(fā)現(xiàn)可以直接維護兩個單調(diào)隊列，我們可以遍歷一遍整個序列，然后以當前位置i為連續(xù)區(qū)間結(jié)束的位置，接下來我們該怎么找連續(xù)區(qū)間開始的位置呢？我們維護的兩個單調(diào)隊列，一個維護最大值，一個維護最小值，這樣我們比較一下最大值和最小值的差，若其差值大于k的話，那么我們可以選擇減小最大值或者增大最小值兩個選項來縮小這個差值，選擇哪一個選項取決與最大值和最小值的下標哪一個更靠前，這也是為了維護該連續(xù)區(qū)間的可行性，這樣不斷的將區(qū)間縮小，直到當前區(qū)間內(nèi)的差值滿足小于等于k這個條件，注意，若假設(shè)mmax.front()為最大值的下標，我們將其刪掉后，可行區(qū)間變成了[mmax.front()+1,i]，而不是[mmax.front(),i]，注意一下這個+1

其實一開始我也是不太理解這個+1的，還是在這里再說一下我自己的理解吧，假設(shè)現(xiàn)在最大值和最小值之間的差值大于k，我們將要選擇刪掉最大值以減小差值，這樣一來我們刪掉的肯定是mmax.front()這個下標，若這個下標被刪掉后，將會出現(xiàn)兩種可能，新區(qū)間的最大值就是剛才被刪除下標的后一位，另一種可能就是被刪除下標的后一位并不是新區(qū)間的最大值，無論是這兩種情況之中的哪一種，肯定都滿足新區(qū)間中最大值和最小值之間的差值變小了，所以在刪除掉第一個下標后新區(qū)間的范圍變成了[mmax.front()+1,l]，這樣維護好整個區(qū)間后，我們最后判斷一下這個差值是否大于等于m，若大于等于m，直接更新答案即可

有一個小細節(jié)，這個題目沒有保證數(shù)據(jù)一定有解，會出現(xiàn)答案為0的情況，也就是所有區(qū)間都不滿足條件，這個時候要輸出0，我一開始看到題目要求最大值，就直接把答案設(shè)置為負無窮，這也導(dǎo)致我無解的情況會輸出負無窮而不是0，因為這個小細節(jié)調(diào)了半個小時，也是有點自閉的

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<deque> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int a[N];int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,m,k;while(scanf("%d%d%d",&n,&m,&k)!=EOF){for(int i=1;i<=n;i++)scanf("%d",a+i);deque<int>mmax;//維護最大值的單調(diào)隊列，維護的是下標deque<int>mmin;//維護最小值的單調(diào)隊列，維護的是下標int mark=1,ans=0;for(int i=1;i<=n;i++){while(mmax.size()&&a[mmax.back()]<=a[i])mmax.pop_back();mmax.push_back(i);while(mmin.size()&&a[mmin.back()]>=a[i])mmin.pop_back(); mmin.push_back(i);while(mmax.size()&&mmin.size()&&a[mmax.front()]-a[mmin.front()]>k)//如果差值大于k的話，刪除掉最大值或最小值{if(mmax.front()<mmin.front()){mark=mmax.front()+1;//更新可行區(qū)間mmax.pop_front();}else{mark=mmin.front()+1;//更新可行區(qū)間mmin.pop_front();}}if(mmax.size()&&mmin.size()&&a[mmax.front()]-a[mmin.front()]>=m)//更新答案{ans=max(ans,i-mark+1);}}printf("%d\n",ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 3530 Subsequence(单调队列+思维)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。