BOJ. Find Minimum (11003)

[Link] https://www.acmicpc.net/problem/11003

Approach

For each position i, the required window is [max(0, i - L + 1), i]. In particular, the first L - 1 windows contain only the values seen so far; they are not padded with nonexistent elements.

Keep candidate indices in increasing order in a deque, with their values in a parallel primitive array. Before inserting A[i], remove indices <= i - L from the front because they are outside the current window. Then remove values greater than or equal to A[i] from the back: the new value is no larger and remains in the window at least as long, so those candidates can never be a future minimum. The front value is therefore the minimum for the current window. Removing equal values is safe and keeps only the newest copy.

Each index is inserted once and removed at most once, so the total work is O(N) amortized. The input scanner reads bytes directly, and the deque uses two int[] arrays, avoiding per-number strings and per-element objects. The arrays and output buffer use O(N) memory.

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int n = input.nextInt();
        int windowLength = input.nextInt();
        int[] indices = new int[n];
        int[] values = new int[n];
        int front = 0;
        int back = 0;
        StringBuilder output = new StringBuilder();

        for (int i = 0; i < n; i++) {
            int value = input.nextInt();

            while (front < back && indices[front] <= i - windowLength) {
                front++;
            }
            while (front < back && values[back - 1] >= value) {
                back--;
            }

            indices[back] = i;
            values[back] = value;
            back++;

            if (i > 0) {
                output.append(' ');
            }
            output.append(values[front]);
        }

        System.out.println(output);
    }

    private static class FastScanner {
        private final BufferedInputStream in = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int pointer;
        private int length;

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ');

            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }

            int value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
            return value * sign;
        }

        private int read() throws IOException {
            if (pointer == length) {
                length = in.read(buffer);
                pointer = 0;
                if (length == -1) {
                    return -1;
                }
            }
            return buffer[pointer++];
        }
    }
}