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);
        }
    }
}