POJ - 2823 Sliding Window（单调队列）-白红宇

POJ - 2823 Sliding Window（单调队列）

阅读量：5129 次

发布时间：2019-06-13

本文共 1928 字，大约阅读时间需要 6 分钟。

题意：从左到右，分别求出长度为k的各滑动窗口中的最大值和最小值。

分析：据说C++能过，G++超时。。

1、双向队列q1记录的是下标，便于求最小值，在滑动窗口后移的过程中，判断q1.back()处的元素，若大于等于a[i]（待加入队列的元素），则弹出（因为若比待加入元素大，则一定不是当前滑动窗口的最小值），同时要保证当前队列中的所有元素位置都要位于当前滑动窗口中，所以将不符合的q1.pop_front();

2、q2同理，求最大值。

3、实质上，上述操作后q1中形成的是单增队列，队首是最小值，q2相反。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #define Min(a, b) ((a < b) ? a : b)#define Max(a, b) ((a < b) ? b : a)const double eps = 1e-8;inline int dcmp(double a, double b){ if(fabs(a - b) < eps) return 0; return a > b ? 1 : -1;}typedef long long LL;typedef unsigned long long ULL;const int INT_INF = 0x3f3f3f3f;const int INT_M_INF = 0x7f7f7f7f;const LL LL_INF = 0x3f3f3f3f3f3f3f3f;const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};const int MOD = 1e9 + 7;const double pi = acos(-1.0);const int MAXN = 1000000 + 10;const int MAXT = 10000 + 10;using namespace std;deque
                      
                        q1, q2;int a[MAXN], mi[MAXN], ma[MAXN];int n, k;void solve(){ for(int i = 0; i < n; ++i){ while(!q1.empty() && a[q1.back()] >= a[i]){ q1.pop_back(); } q1.push_back(i); while(!q1.empty() && q1.front() <= i - k){ q1.pop_front(); } while(!q2.empty() && a[q2.back()] <= a[i]){ q2.pop_back(); } q2.push_back(i); while(!q2.empty() && q2.front() <= i - k){ q2.pop_front(); } if(i >= k - 1){ mi[i] = a[q1.front()]; ma[i] = a[q2.front()]; } }}int main(){ scanf("%d%d", &n, &k); for(int i = 0; i < n; ++i){ scanf("%d", &a[i]); } solve(); for(int i = k - 1; i < n; ++i){ if(i != k - 1) printf(" "); printf("%d", mi[i]); } printf("\n"); for(int i = k - 1; i < n; ++i){ if(i != k - 1) printf(" "); printf("%d", ma[i]); } printf("\n"); return 0;}

转载于:https://www.cnblogs.com/tyty-Somnuspoppy/p/6749178.html

你可能感兴趣的文章