单调队列和单调栈

　　最近学到了dp，一开始以为思维的体操是时候绽放了....

　　傲娇.jpg

　　....但是....

　　下面回归正题：

单调队列：单调队列分为两种，即单调递增和单调递减队列，简单的理解就是基本队列赋予严格的递增或递减的单调性即可。

　　单调队列一般用于优化，一般有如下用途。

　　下面给一道单调队列的模版题：

　题目链接:

　　题意：意思就是给出一个区间长度k和n个元素的数组a，从a的第一个k大小的连续区间开始直到最后一个连续区间，找到每次区间里的最大值和最小值，具体输出形式见题面。

　　本题思路：刚好满足单调队列的性质，每次维护区间内的最值并保存就ok。

　　参考代码：

 1 #include <iostream>
 2 #include <deque>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 typedef pair<int ,int > P;
 7 const int maxn = 1e6 + 5;
 8 int a[maxn], n, k, Max[maxn], Min[maxn], nummax = 0, nummin = 0;
 9 
10 void getMax() {
11     deque <P> p;
12     P now;
13     p.push_front(make_pair(a[0], 0));
14     if(k == 1) Max[nummax ++] = a[0];
15     for(int i = 1; i < n; i ++) {
16         now = p.back();
17         while(now.first < a[i]) {
18             p.pop_back();
19             if(!p.empty())
20                 now = p.back();
21             else break;
22         }
23         p.push_back(make_pair(a[i], i));
24         if(i - p.front().second > k - 1) p.pop_front(); 
25         if(i > k - 2) Max[nummax ++] = p.front().first; 
26     }
27 }
28 
29 void getMin() {
30     if(k == 1) Min[nummin ++] =  a[0];
31     deque <P> p;
32     P now;
33     p.push_front(make_pair(a[0], 0));
34     for(int i = 1; i < n; i ++) {
35         now = p.back();
36         while(now.first > a[i]) {
37             p.pop_back();
38             if(!p.empty()) now = p.back();
39             else break;
40         }
41         p.push_back(make_pair(a[i], i));
42         if(i - p.front().second > k - 1) p.pop_front();
43         if(i > k - 2) Min[nummin ++] = p.front().first;
44     }
45 }
46 
47 int main () {
48     ios::sync_with_stdio(false);
49     cin >> n >> k;
50     for(int i = 0; i < n; i ++) cin >> a[i];
51     getMax();
52     getMin();
53     for(int i = 0; i < nummin ; i ++) {
54         if(i > 0) cout << ' ';
55         cout << Min[i];
56     }
57     cout << endl;
58     for(int i = 0; i < nummax; i ++) {
59         if(i > 0) cout << ' ';
60         cout << Max[i];
61     }
62     cout << endl;
63     return 0;
64 }

View Code

　　下面给出数组模拟队列版本的参考代码吧：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 typedef pair<int ,int > P;
 5 const int maxn = 1e6 + 5;
 6 int a[maxn], n, k, Max[maxn], Min[maxn], nummax = 0, nummin = 0;
 7 P v[maxn];
 8 
 9 void getMin() {
10     int i, head = 1, tail = 0;
11     for(i = 0; i < k - 1; i ++) {
12         while(head <= tail && v[tail].first >= a[i]) tail --;
13         v[++ tail].first = a[i], v[tail].second = i;
14     }
15     for(; i < n; i ++) {
16         while(head <= tail && v[tail].first >= a[i]) tail --;
17         v[++tail].first = a[i], v[tail].second = i;
18         while(i - v[head].second > k - 1) head ++;
19         Min[nummin ++] = v[head].first;
20     }
21 }
22 
23 void getMax() {
24     int i, head = 1, tail = 0;
25     for(i = 0; i < k - 1; i ++) {
26         while(head <= tail && v[tail].first <= a[i]) tail --;
27         v[++ tail].first = a[i], v[tail].second = i;
28     }
29     for(; i < n; i ++) {
30         while(head <= tail && v[tail].first <= a[i]) tail --;
31         v[++ tail].first = a[i], v[tail].second = i;
32         while(i - v[head].second > k - 1) head ++;
33         Max[nummax ++] = v[head].first;
34     }
35 }
36 
37 int main () {
38     ios::sync_with_stdio(false);
39     cin >> n >> k;
40     for(int i = 0; i < n; i ++) cin >> a[i];
41     getMin();
42     getMax();
43     for(int i = 0; i < nummin ; i ++) {
44         if(i > 0) cout << ' ';
45         cout << Min[i];
46     }
47     cout << endl;
48     for(int i = 0; i < nummax; i ++) {
49         if(i > 0) cout << ' ';
50         cout << Max[i];
51     }
52     cout << endl;
53     return 0;
54 }

View Code

单调栈：单调栈和单调队列的定义类似，也可以简单理解为基本的栈赋予严格的递增或递减单调性即可。

单调栈的本质为：当一个数a在另一个数b前面且比b大，那么数a就在找第一个比某数小的问题里就完全没有考虑的必要了，他被b完全屏蔽了。所以利用单调栈，可以找到从左或右第一个比某个值小或大的元素的位置。