题解 | 火星探测器稳定性分析

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

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        Integer[] a = new Integer[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        int left = 0;
        int bestLen = 0;
        Deque<Integer> maxQ = new ArrayDeque<>();
        Deque<Integer> minQ = new ArrayDeque<>();
        List<int[]> ans = new ArrayList<>();
        for (int right = 0; right < n; right++) {
            int v = a[right];
            if (v < 18 || v > 24) {
                maxQ.clear();
                minQ.clear();
                left = right + 1;
                continue;
            }
            while (!minQ.isEmpty() && a[minQ.peekLast()] >= v) {
                minQ.pollLast();
            }
            minQ.addLast(right);
            while (!maxQ.isEmpty() && a[maxQ.peekLast()] <= v) {
                maxQ.pollLast();
            }
            maxQ.addLast(right);
            while (left <= right && a[maxQ.peekFirst()] - a[minQ.peekFirst()] > 4) {
                if (maxQ.peekFirst() == left) {
                    maxQ.pollFirst();
                }
                if (minQ.peekFirst() == left) {
                    minQ.pollFirst();
                }
                left++;
            }
            int len = right - left + 1;
            if (len > 0) {
                if (len > bestLen) {
                    bestLen = len;
                    ans.clear();
                    ans.add(new int[] {left, right});
                } else if (len == bestLen) {
                    ans.add(new int[] {left, right});
                }
            }
        }
        if (ans.isEmpty()) {
            return;
        }
        StringBuilder sb = new StringBuilder();
        for (int[] p : ans) {
            sb.append(p[0]).append(" ").append(p[1]).append(System.lineSeparator());
        }
        System.out.print(sb.toString());
    }
}