1126. Magnetic Storms（单调队列）

一开始扫描数组，时间复杂度O(n)，然后找最大值用max_element,时间复杂度O（mlogm),总的时间复杂度O(nmlogm),直接TLE2，后来上网查到要用线段树或者单调队列才能过，学一下单调队列。

http://wenku.baidu.com/view/f88397a50029bd64783e2c5c.html一个挺好的单调队列的课件，有助于理解。

单调对列：单调队列是特殊的双端队列，元素是单调递减或者单调递增的，并且元素下标是单调递增的。

（单调队列需要两端删除，队尾插入）

常用操作：（1）插入:若新元素从队尾插入后会破坏单调性，则删除队尾元素，直到插入后不在破坏单调性，再将其插入单调队列。

(2)获取最大或最小值：访问队首元素。

维护方法：删除的时候，判断队首，如果队首元素下标小于当前段左边界就删除，不断删除队首直到队首元素下标大于等于当前段左边界。在每次插入的时候，先判断队尾元素，如果不比待插入元素大就删除，不断删除队尾直到队尾元素大于待插入元素或者队空。此时直接输出队首元素就行了。　

用stl做可以省去开大数组的空间：

 1 #include <cstdio>
 2 #include <deque>
 3 using namespace std;
 4 struct Node                    
 5 {
 6     int value, index;
 7 };                        //存储每个元素的数值和下标
 8 int main()
 9 {
10     int m;
11     scanf("%d", &m);
12     Node node;
13     deque<Node> dqN;
14     int num = 0;
15     while (scanf("%d", &node.value) && node.value != -1)
16     {
17         node.index = num++;
18         while (!dqN.empty() && dqN.front().index < num - m) 
19             dqN.pop_front();
20         while (!dqN.empty() && dqN.back().value < node.value)
21             dqN.pop_back();
22         dqN.push_back(node);
23         if (num >= m)                                         //超出限定的m输出队首元素
24             printf("%d\n", dqN.front().value);
25     }
26     system("pause");
27     return 0;
28 }

用数组模拟（需要开两个数组）：

#include <cstdio>
#include <iostream>
int main()
{
    int ele[250001] = {0}, index[250001] = {0};
    int m;
    scanf("%d", &m);
    int front = 1, back = 1;             //模拟队首队尾指针
    for (int i = 1;  ; ++i)
    {
        int t;
        scanf("%d", &t);
        if (t == -1)
            return 0;
        while (front <= back && i - index[front] >= m)
            ++front;
        while (back >= front && ele[back] < t)
            --back;
        ele[++back] = t;
        index[back] = i;
        if (i >= m)
            printf("%d\n", ele[front]);
    }
    system("pause");
    return 0;
}