2 단 대기 열 (deque) 의 응용

질문 설명: (미끄럼 최소 값)
 주어진 길이 n 의 수열 a0, a1, a2. an - 1 과 하나의 정수 k, 수열 bi = min (ai, ai + 1. ai + k - 1) {i = 0, 1,. n - k} {1<=k<=n<=1e6;0<=ai<=1e9}  sample input  n=5  k=3  a={1,3,5,4,2}  sample ouput  b = {1, 3, 2} [분석]:    solution 1:         RMQ: 복잡 도 O (nlogn)    solution 2:         deque < 2 단 대기 열: 머리 와 꼬리 에 요 소 를 삽입 하고 삭제 할 수 있 는 데이터 구조 > O (n) 시간 내 에 해결 [사고]:    처음에 양 끝 대기 열 이 비어 있 었 습 니 다. 그리고 양 끝 대기 열 을 계속 유지 하여 다음 순서 로 유지 합 니 다. 뒤에 있 는 최소 값 의 a 배열 요 소 를 저장 하 는 것 에 주의 하 십시오.
    머리 에서 시작 하 는 요 소 를 xi 로 설정 하면 xi < xi + 1 & & a (xi) < a (xi + 1)    우선, b0 을 계산 하기 위해 0 에서 k - 1 을 순서대로 대열 에 가입 하고 i 에 가입 할 때 쌍 단 대열 의 끝 값 j 가 aj > = ai 를 만족 시 키 면 계속 꺼 냅 니 다.    2 단 대기 열 이 비어 있 거나 aj < ai 가 끝 날 때 까지 i 를 추가 합 니 다.         k - 1 이 모두 대기 열 에 들 어가 서 대기 열 머리의 값 j 를 보면 b0 = aj, 만약 j = = 0 이 라면 그 후의 계산 은 사용 되 지 않 기 때문에 삭제 합 니 다.    그 다음 에 bi 를 계산 하기 위해 서 는 대열 의 끝 에 k 를 넣 고 요 소 를 계속 넣 으 면 뒤의 bi 의 값 을 계산 할 수 있 습 니 다. 쌍 단 대열 의 가입 과      삭 제 는 모두 O (n) 회 진행 되 었 기 때문에 알고리즘 복잡 도 O (n)    샘플 에 대해 대기 열 시 뮬 레이 션 은 다음 과 같 습 니 다.    add 0 - > {0} (아래 표 시 를 저장 합 니 다)    add 1 -> {0,1}     add 2 -> {0,1,2}     b0=a0 =1;     remove 0 -> {1,2}     add 3 - > {1, 3} (a2 > = a3, 따라서 삭제 2)    b1=a1=3;     remove 1 -> {3}     add 4 -> {4}  (a3 > = a4, 따라서 삭제 3)    b2 = a4 = 2 코드 구현: 

//  
int n,k;
int a[maxn],b[maxn];
int deq[maxn];//    
void solve()
{
    int s=0,t=0; //          
    for(int i=0; i<n; ++i)
    {
        //          i
        while(s<t&&a[deq[t-1]]>=a[i]) t--;
        deq[t++]=i; 
        if(i-k+1>=0)
        {
            b[i-k+1]=a[deq[s]];
            if(deq[s]==i-k+1) s++;//            
        }
    }
    for(int i=0; i<=n-k; ++i)
    {
        printf("%d%c",b[i],i==n-k?'
':' ');
    }
}