单调队列经典题目直接上代码

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 const int sz = 1000010; 6 int n, k; 7 int q[sz], p[sz], a[sz]; 8 void work_min() { 9     int head = 1, tail = 0;10     for(int i = 1; i <= n; i++) {11         while(head <= tail && q[tail] >= a[i]) tail--;12         q[++tail] = a[i];13         p[tail] = i;14         while(p[head] <= i-k) head++;15         if(i >= k) printf("%d ", q[head]);16     }17     printf("\n");18 }19 void work_max() {20     int head = 1, tail = 0;21     for(int i = 1; i <= n; i++) {22         while(head <= tail && a[i] >= q[tail]) tail--;23         q[++tail] = a[i];24         p[tail] = i;25         while(p[head] <= i-k) head++;26         if(i >= k) printf("%d ", q[head]);27     }28     printf("\n");29 }30 int main() {31     scanf("%d%d", &n, &k);32     for(int i = 1; i <= n; i++)33         scanf("%d", &a[i]);34     work_min();35     work_max();36     return 0;37 }