单调队列

单调队列是什么呢？可以直接从问题开始来展开。
Poj 2823
给定一个数列，从左至右输出每个长度为m的数列段内的最小数和最大数。
数列长度：N<=106，m<=N

暴力解

很直观的一种解法，那就是从数列的开头，将窗放上去，然后找到这最开始的k个数的最大值，然后窗最后移一个单元，继续找到k个数中的最大值。

#include <iostream>
#include <cstdio>
using namespace std ;
const int MAX = 105 ;
struct node{
  int index ;
  int minn ;
  int maxx ;
};

int main()
{

  int a[MAX] ;
  node ans[MAX] ;
  int n ,m ;
  int k = 1 ;
  cin >> n >> m ;
  for(int i = 1 ; i<=n ;i++)
  {
    cin >>a[i] ;
  }
  for(int i = 1 ; i<=n-m+1; i++)
  {
    int maxn = -0x3f3f3f3f ;
    int minn = 0x3f3f3f3f ;
    for(int j = i; j<=i+m-1 ;j++)
    {
      
      maxn = max(a[j],maxn);
      minn = min(a[j],minn) ;
      
    }
    node s ;
    s.index = i  ;
    s.minn = minn ;
    s.maxx = maxn ;
    ans[k++] =s;

  }
  for(int i = 1 ; i<=k-1 ;i++)
  {
    cout<<ans[i].index <<" : " <<" min :"<< ans[i].minn<<" max : "<<ans[i].maxx <<endl ;
  }
  
  
  
  return 0 ;
}

单调队列解: 

对于单调队列，我们这样子来定义：

• 1、维护区间最值
• 2、去除冗杂状态 如上题，区间中的两个元素a[i],a[j]（假设现在再求最大值）
  若 j>i且a[j]>=a[i] ，a[j]比a[i]还大而且还在后面（目前a[j]留在队列肯定比a[i]有用，因为你是往后推， 核心思想 !!!）
• 3、保持队列单调，最大值是单调递减序列，最小值反之
• 4、最优选择在队首

单调队列实现的大致过程：
1、维护队首（对于上题就是如果队首已经是当前元素的m个之前，则队首就应该被删了,head++）
2、在队尾插入（每插入一个就要从队尾开始往前去除冗杂状态，保持单调性）

简单举例应用
数列为：6 4 10 10 8 6 4 2 12 14
N=10,K=3;
那么我们构造一个长度为3的单调递减队列：
首先，那6和它的位置0放入队列中，我们用(6,0)表示，每一步插入元素时队列中的元素如下
插入6：(6,0);
插入4：(6,0),(4,1);
插入10：(10,2);
插入第二个10，保留后面那个：(10,3);
插入8：(10,3),(8,4);
插入6：(10,3),(8,4),(6,5);
插入4，之前的10已经超出范围所以排掉：(8,4),(6,5),(4,6);
插入2，同理：(6,5),(4,6),(2,7);
插入12：(12,8);
插入14：(14,9);
那么f(i)就是第i步时队列当中的首元素：6,6,10,10,10,10,8,6,12,14
同理，最小值也可以用单调队列来做。

单调队列的时间复杂度是O（N），因为每个数只会进队和出队一次，所以这个算法的效率还是很高的。
注意：建议直接用数组模拟单调队列，因为系统自带容器不方便而且不易调试，同时，每个数只会进去一次，所以，数组绝对不会爆，空间也是S（N），优于堆或线段树等数据结构。

更重要的：单调是一种思想，当我们解决问题的时候发现有许多冗杂无用的状态时，我们可以采用单调思想，用单调队列或类似于单调队列的方法去除冗杂状态，保存我们想要的状态.

#include <iostream>
#include <cstdio>
using namespace std ;
const int MAX = 1005 ;
struct Num{
  int index ;// 需要记录单调队列内的下标
  int x ;// 大小 ;
};
int a[MAX]; // 原始队列
Num q[MAX]; // 单调队列
int n ,m ;

void Getmax()
{
  // 求最大值,是单调递减,队首就是最大值
  // 1  每次加一个新数,就要维护一次递减队列,
  // 2  从队尾开始向队首弹比当前加入的新数要小的元素 ,
  // 3  保证队列长度为 m
  int front , back ;
  front = 1 ;
  back= 0 ;
  for(int i = 1 ; i<=n ; i++)
  {
    if(front >back)
    // 队列为空
    printf("0 ");
    else
    {
      if(q[front].index +m <i)
      front++;
      printf("%d ",q[front].x);

    }
    while(front<=back && q[back].x<=a[i])
    // 当队列非空的时候  ,不断弹出队尾比当前小的元素,维护一个单调
    // 递减的队列 ;
    back-- ;
    back++ ;
    q[back].x = a[i] ;// 加入队列
    q[back].index = i ;

  }


  
}
void getmin()
{
    int front , back ;
  front = 1 ;
  back= 0 ;
  for(int i = 1 ; i<=n ; i++)
  {
    if(front >back)
    printf("0 ");
    else
    {
      if(q[front].index +m <i)
      front++;
      printf("%d ",q[front].x);

    }
    while(front<=back && q[back].x>=a[i])

    back-- ;
    back++ ;
    q[back].x = a[i] ;// 加入队列
    q[back].index = i ;

  }
  
  
}
int main()
{

  cin >> n >> m ;
  for(int i = 1 ; i<=n; i++)
  cin >>a[i] ;
  Getmax() ;// 求最大 , 维护递减队列


  return 0 ;
}

 模板题 ​​https://cn.vjudge.net/problem/POJ-2823​​

// File Name: deque.cpp
// Author: xiaxiaosheng
// Created Time: 2018年12月21日 星期五 23时16分47秒

#include<deque>
#include<stack>
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>

using namespace std;
const int MAX = 1e6+10 ; 

struct node{
    int x ; 
    int index ; 
}q[MAX];
int a[MAX] ; 
int n , m ; 
int mx[MAX] ,mn[MAX] ; 
void getmin()
{
    int i , head = 1  , tail = 0 ; 
    for(i = 1 ; i<m ; i++) 
    {
        // 先将前m－1个数放入队列  , 每次都要维护递增队列,
        while(head<=tail && tail && q[tail].x >=a[i])  tail-- ; 
        q[++tail].x = a[i] ; 
        q[tail].index = i ; 
    }
    for(; i<=n ;i++) 
    {
        while(head<=tail && q[tail].x >=a[i] ) tail-- ; 
        q[++tail].x = a[i]  ; 
        q[tail].index = i ; 
        while(q[head].index <i -m + 1) 
            head++ ;
        mn[i-m+1] = q[head].x ;
    }
    return ; 
}
void getmax()
{
    int i ; 
    int head = 1 , tail = 0 ; 
    for(i = 1 ;i<m ; i++) 
    {
        while(head<=tail && q[tail].x<=a[i]) tail-- ;
        q[++tail].x = a[i] ; 
        q[tail].index = i ;
    }
    for(;i<=n;i++)
    {
        while(head<=tail&& q[tail].x <=a[i] ) tail-- ;
        q[++tail].x = a[i ] ; 
        q[tail].index = i ; 
        while(q[head].index <i-m+1 ) head++ ;
        mx[i-m+1] = q[head].x ; 
    }
    return ; 
}

int main()
{
    cin >> n >> m ;
    for(int i = 1 ; i<=n ; i++) 
        cin >> a[i] ; 
    getmin();
    getmax();
    for(int i = 1 ; i<= n-m+1 ; i++ ) 
    {
        if(i ==1 ) 
            printf("%d",mn[i]);
        else
            printf(" %d",mn[i]) ; 
    }
    printf("\n");
    for(int i = 1 ; i<=n-m+1 ;i++)  
    {
        if(i ==1 ) 
        {
            printf("%d",mx[i] ); 
        }
        else
            printf(" %d",mx[i]) ; 
        
    }
    return 0;
}

考试周,先学这些吧....