火星探测器稳定性分析

题意

给定 $n$ 个环境稳定性指数（整数，范围 $[0, 30]$ ），找出最长的连续子数组，满足：

所有元素都在 $[18, 24]$ 内
子数组内最大值与最小值的差 $\le 4$

如果有多个等长的最长子数组，按起始索引从小到大输出。索引从 $0$ 开始。

思路

两个约束怎么同时处理？

先看第一个约束：每个元素都要在 $[18, 24]$ 内。这意味着一旦碰到范围外的元素，窗口就必须断开重新开始——这个元素是天然的分割点。

再看第二个约束：窗口内 $\max - \min \le 4$ 。这是经典的"最大值减最小值不超过阈值的最长子数组"问题，用滑动窗口 + 单调队列解决。

具体做法：维护一个左端点 left，右端点 right 从左往右扫。遇到不在 $[18, 24]$ 的元素，直接跳过并重置左端点。对于合法元素，用两个单调队列分别维护窗口内的最大值和最小值。当 $\max - \min > 4$ 时，收缩左端点，直到满足条件。

每步检查当前窗口长度是否刷新了最优解，记录所有最优的起止索引即可。

时间复杂度 $O(n)$ ，每个元素最多进出队列各一次。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    vector<int> a(n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);

    int bestLen = 0;
    vector<pair<int,int>> results;
    int left = 0;
    deque<int> maxq, minq;

    for(int right = 0; right < n; right++){
        if(a[right] < 18 || a[right] > 24){
            left = right + 1;
            maxq.clear();
            minq.clear();
            continue;
        }
        while(!maxq.empty() && a[maxq.back()] <= a[right]) maxq.pop_back();
        maxq.push_back(right);
        while(!minq.empty() && a[minq.back()] >= a[right]) minq.pop_back();
        minq.push_back(right);

        while(a[maxq.front()] - a[minq.front()] > 4){
            left++;
            if(maxq.front() < left) maxq.pop_front();
            if(minq.front() < left) minq.pop_front();
        }

        int len = right - left + 1;
        if(len > bestLen){
            bestLen = len;
            results.clear();
            results.push_back({left, right});
        } else if(len == bestLen){
            results.push_back({left, right});
        }
    }

    for(auto& p : results)
        printf("%d %d\n", p.first, p.second);
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();

        int bestLen = 0;
        List<int[]> results = new ArrayList<>();
        int left = 0;
        Deque<Integer> maxq = new ArrayDeque<>();
        Deque<Integer> minq = new ArrayDeque<>();

        for (int right = 0; right < n; right++) {
            if (a[right] < 18 || a[right] > 24) {
                left = right + 1;
                maxq.clear();
                minq.clear();
                continue;
            }
            while (!maxq.isEmpty() && a[maxq.peekLast()] <= a[right]) maxq.pollLast();
            maxq.addLast(right);
            while (!minq.isEmpty() && a[minq.peekLast()] >= a[right]) minq.pollLast();
            minq.addLast(right);

            while (a[maxq.peekFirst()] - a[minq.peekFirst()] > 4) {
                left++;
                if (maxq.peekFirst() < left) maxq.pollFirst();
                if (minq.peekFirst() < left) minq.pollFirst();
            }

            int len = right - left + 1;
            if (len > bestLen) {
                bestLen = len;
                results.clear();
                results.add(new int[]{left, right});
            } else if (len == bestLen) {
                results.add(new int[]{left, right});
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int[] p : results)
            sb.append(p[0]).append(' ').append(p[1]).append('\n');
        System.out.print(sb);
    }
}

import sys
from collections import deque

def main():
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))

    best_len = 0
    results = []
    left = 0
    maxq = deque()
    minq = deque()

    for right in range(n):
        if a[right] < 18 or a[right] > 24:
            left = right + 1
            maxq.clear()
            minq.clear()
            continue

        while maxq and a[maxq[-1]] <= a[right]:
            maxq.pop()
        maxq.append(right)
        while minq and a[minq[-1]] >= a[right]:
            minq.pop()
        minq.append(right)

        while a[maxq[0]] - a[minq[0]] > 4:
            left += 1
            if maxq[0] < left:
                maxq.popleft()
            if minq[0] < left:
                minq.popleft()

        length = right - left + 1
        if length > best_len:
            best_len = length
            results = [(left, right)]
        elif length == best_len:
            results.append((left, right))

    print('\n'.join(f"{l} {r}" for l, r in results))

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    const n = parseInt(lines[0]);
    const a = lines[1].split(' ').map(Number);

    let bestLen = 0;
    const results = [];
    let left = 0;
    const maxq = [], minq = [];
    let mxH = 0, mnH = 0;

    for (let right = 0; right < n; right++) {
        if (a[right] < 18 || a[right] > 24) {
            left = right + 1;
            maxq.length = 0; mxH = 0;
            minq.length = 0; mnH = 0;
            continue;
        }
        while (mxH < maxq.length && a[maxq[maxq.length - 1]] <= a[right]) maxq.pop();
        maxq.push(right);
        while (mnH < minq.length && a[minq[minq.length - 1]] >= a[right]) minq.pop();
        minq.push(right);

        while (a[maxq[mxH]] - a[minq[mnH]] > 4) {
            left++;
            if (maxq[mxH] < left) mxH++;
            if (minq[mnH] < left) mnH++;
        }

        const len = right - left + 1;
        if (len > bestLen) {
            bestLen = len;
            results.length = 0;
            results.push([left, right]);
        } else if (len === bestLen) {
            results.push([left, right]);
        }
    }

    console.log(results.map(([l, r]) => l + ' ' + r).join('\n'));
});

复杂度

时间复杂度： $O(n)$ ，滑动窗口扫一遍，每个元素进出单调队列各至多一次。
空间复杂度： $O(n)$ ，单调队列和结果数组。