# Sliding Window

This problem is the same as Slinding Window Maximum. But as to run more fast and avoid TLE error on POJ, we have to use a StringBuffer to speed up string IO.

import java.io.*;
import java.util.*;

public class SlidingWindow {
private static int[] a;
private static int[] deq;

private static void solve(int n, int k) {
int s = 0, t = 0;

StringBuffer sbuf = new StringBuffer(n * 5);
// output minimum values
for (int i = 0; i < n; i++) {
while (s < t && deq[s] <= i - k) s++;
while (s < t && a[deq[t - 1]] >= a[i]) t--;

deq[t++] = i;

if (i == k - 1) sbuf.append(a[deq[s]]);
else if (i >= k) {
sbuf.append(' ');
sbuf.append(a[deq[s]]);
}
}

System.out.println(sbuf.toString());

// empty dequeue
s = 0;
t = 0;
sbuf.setLength(0);

// output maximum values
for (int i = 0; i < n; i++) {
while (s < t && deq[s] <= i - k) s++;
while (s < t && a[deq[t - 1]] <= a[i]) t--;

deq[t++] = i;

if (i == k - 1) sbuf.append(a[deq[s]]);
else if (i >= k) {
sbuf.append(' ');
sbuf.append(a[deq[s]]);
}
}

System.out.println(sbuf.toString());
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int n = in.nextInt(), k = in.nextInt();
a = new int[n];
deq = new int[n + 5];
for (int i = 0; i < n; i++) {
a[i] = in.nextInt();
}
solve(n, k);
}
}
}