以最大值为例，既然我们想要保证队列开头为答案，那么我们就要保证每次更新使最大值一直放在队列。那么如果存储的最大值该弹出了怎么办呢？我们只需要记录下每个元素的位置，判断是否在区间内即可。
队头弹出后，第二位就变成了队头，我们就要保证这个数现在是区间内最大。那么是不是说，我们需要将这个长度为 $ k $ 的区间中的每一个数都存起来呢？不是的，并不是每个数被记录都有意义的。举个例子， $ a_i $ 和 $ a_j $ 两个数， $ i<j $ 。如果 $a_i >a_j $，那么两个数都应该记录；但是如果 $ a_i≤a_j $ ，那么当 $ a_j $ 进入区间后， $ a_i $ 的记录就没有意义了。很好理解，我们假设每个数作为区间最大值的次数为它的贡献，当 $ a_j $ 进入区间以后，在区间中存在的时间一定比 $ a_i $ 长，也就说明 $ a_i $ 一定不会再做贡献了，我们确定没有贡献的点，便可以直接删去，以维护单调队列的单调性。
#include#include #include #include #include #define re registerusing namespace std ;const int maxn = 1e6 + 5 ;inline int read () { int f = 1 , x = 0 ; char ch = getchar () ; while ( ch > '9' || ch < '0' ) {if(ch == '-') f = -1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) {x = (x << 1) + (x << 3) + ch - '0' ; ch = getchar () ; } return x * f ;}int n , k , a[maxn] ;int head = 1 , tail ;struct Node { int val , pos ;}q[maxn] ;int main () { n = read () ; k = read () ; for(re int i = 1 ; i <= n ; ++ i) {a[i] = read () ;} for(re int i = 1 ; i <= n ; ++ i) { while(head <= tail && q[head].pos + k <= i) ++head ; while(head <= tail && q[tail].val >= a[i]) --tail ; q[++tail].val = a[i] ; q[tail].pos = i ; if(i >= k) printf("%d " , q[head].val) ; } head = 1 , tail = 0 ; printf("\n") ; for(re int i = 1 ; i <= n ; ++ i) { while(head <= tail && q[head].pos + k <= i) ++head ; while(head <= tail && q[tail].val <= a[i]) --tail ; q[++tail].val = a[i] ; q[tail].pos = i ; if(i >= k) printf("%d " , q[head].val) ; } return 0 ;}