[PKU2823]Sliding Window

赤裸裸的单调队列。分别用一个单调递减和一个单调递增的队列来维护最大值和最小值，当队头元素的位置与i的差超过k那就丢弃头。每一次插入i时都要维护单调性，之后输入队列的头元素。

下面的程序用了STL的双端队列deque，和写数组没什么差别，略去了头尾指针而已。其实STL有优先队列，只不过应用在这题上面还得写个类才能保证头指针的移动，过于麻烦，还不如自己实现单调队列。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, k;
vector<int> a;
deque<int> Qmin, Qmax;
int main()
{
  ios::sync_with_stdio(false);
  cin >> n >> k;
  for (int i = 0, x; i != n; ++i)
  {
    cin >> x;
    a.push_back(x);
  }

  for (int i = 0; i != k-1; ++i)
  {
    while (!Qmin.empty() && a[Qmin.back()] >= a[i]) Qmin.pop_back();
    while (!Qmax.empty() && a[Qmax.back()] <= a[i]) Qmax.pop_back();
    Qmin.push_back(i);
    Qmax.push_back(i);
  }
  for (int i = k-1; i != n; ++i)
  {
    while (!Qmin.empty() && Qmin.front() <= i-k) Qmin.pop_front();
    while (!Qmin.empty() && a[Qmin.back()] >= a[i]) Qmin.pop_back();
    Qmin.push_back(i);
    cout << a[Qmin.front()] << ' ';
  }
  cout << endl;
  for (int i = k-1; i != n; ++i)
  {
    while (!Qmax.empty() && Qmax.front() <= i-k) Qmax.pop_front();
    while (!Qmax.empty() && a[Qmax.back()] <= a[i]) Qmax.pop_back();
    Qmax.push_back(i);
    cout << a[Qmax.front()] << ' ';
  }
}

Comments