1126. Magnetic Storms（单调队列）

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

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

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

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

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

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

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

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

 1 #include 
 2 #include 
 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 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 
#include 
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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！