題目描述
現在有一堆數字共N個數字（N<=10^6），以及一個大小為k的視窗。現在這個從左邊開始向右滑動，每次滑動一個機關，求出每次滑動後視窗中的最大值和最小值。
例如：
The array is [1 3 -1 -3 5 3 6 7], and k = 3.
輸入輸出格式
輸入格式：
輸入一共有兩行，第一行為n,k。
第二行為n個數(<INT_MAX).
輸出格式：
輸出共兩行，第一行為每次視窗滑動的最小值
第二行為每次視窗滑動的最大值
輸入輸出樣例
輸入樣例#1：
8 3
1 3 -1 -3 5 3 6 7 輸出樣例#1：
-1 -3 -3 -3 3 3
3 3 5 5 6 7 說明
50%的資料，n<=10^5
100%的資料，n<=10^6
感覺自己寫代碼越來越精簡了。
stl裡提供了一種叫做deque的雙端隊列。
這種隊列支援在隊首和隊尾插入或者删除。
這樣正好解決了queue不用應用于單調隊列的缺陷。
關于deque的各種用法。
一張圖足以概覽
對于本題而言。查詢最大最小值其實就是改一下入隊條件的問題，
一個三目運算符解決
#include<iostream>
#include<cstdio>
#include<deque>
using namespace std;
const int MAXN=2000050;
const int maxn=0x7fffffff;
void read(int &n){char c='+';int x=0;bool flag=0;while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
while(c>='0'&&c<='9'){x=x*10+(c-48);c=getchar();}flag==1?n=-x:n=x;}
int n,k;
int a[MAXN];
struct node
{
int w,p;
node (int a,int b) {w=a;p=b;}
};
deque<node>q;
void find(bool how)
{
while(q.size()) q.pop_front();
for(int i=1;i<=n;i++)
{
while(q.size()!=0&&(how==0?(q.back().w<a[i]):(q.back().w>a[i]))) q.pop_back();
q.push_back(node(a[i],i));
while(q.front().p<=(i-k)) q.pop_front();
if(i>=k) printf("%d ",q.front().w);
}
printf("\n");
}
int main()
{
read(n);read(k);
for(int i=1;i<=n;i++) read(a[i]);
find(1);find(0);
return 0;
}
作者：自為風月馬前卒
個人部落格http://attack204.com//
出處：http://zwfymqz.cnblogs.com/
本文版權歸作者和部落格園共有，歡迎轉載，但未經作者同意必須保留此段聲明，且在文章頁面明顯位置給出原文連接配接，否則保留追究法律責任的權利。