阅读量:0
样例输入
8 3 1 3 -1 -3 5 3 6 7
样例输出
-1 -3 -3 -3 3 3 3 3 5 5 6 7
数据范围
对于 20% 的数据，K≤N≤1000；
对于 50% 的数据，K≤N≤10^5；
对于 100% 的数据，K≤N≤10^6。
#include<bits/stdc++.h> using namespace std; int a[1000006]; void yjc(int n, int w) { deque<int> q; for (int i = 0; i < n; ++i) { while (!q.empty() && a[q.back()] <= a[i]) { q.pop_back(); } q.push_back(i); if (i >= w - 1) { cout << a[q.front()] << ' '; if (q.front() == i - w + 1) { q.pop_front(); } } } cout << endl; } void xzh(int n, int w) { deque<int> q; for (int i = 0; i < n; ++i) { while (!q.empty() && a[q.back()] >= a[i]) { q.pop_back(); } q.push_back(i); if (i >= w - 1) { cout << a[q.front()] << ' '; if (q.front() == i - w + 1) { q.pop_front(); } } } cout << endl; } int main() { int n, w; cin >> n >> w; for (int i = 0; i < n; ++i) { cin >> a[i]; } xzh(n, w); yjc(n, w); return 0; }