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

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> s(n);
    for(int i = 0; i < n; i++) {
        cin >> s[i];
    }

    deque<int> maxQ, minQ;
    vector<pair<int, int>> result;
    int bestLen = 0;

    int left = 0, right = 0;
    for(; right < n; right++) {
        // 范围在18-24
        // 如果超出范围，说明当前范围不合法，直接将left移动到right+1处
        // 然后进行continue，right会自动++
        if(!(18 <= s[right] && s[right] <= 24)) {
            minQ.clear();
            maxQ.clear();
            left = right + 1;
            continue;
        }

        // 利用deque维护单调队列
        // 队首始终是当前窗口的 真正最小值/最大值；
        // 队尾存放的是“未来可能的最小/最大”候选，一旦队首滑出，它们马上接任
        while(!maxQ.empty() && s[maxQ.back()] < s[right]) {
            maxQ.pop_back();
        }
        maxQ.push_back(right);
        while(!minQ.empty() && s[minQ.back()] > s[right]) {
            minQ.pop_back();
        }
        minQ.push_back(right);

        // 再处理最值问题，要保证差值为4以内，否则需要缩小范围
        while(!minQ.empty() && !maxQ.empty()
                && s[maxQ.front()] - s[minQ.front()] > 4) {
            if(left == maxQ.front()) maxQ.pop_front();
            if(left == minQ.front()) minQ.pop_front();
            left++;
        }

        // 处理好所有情况，进行结果的判断
        if(left <= right) {
            int len = right - left + 1;
            if(len > bestLen) {
                bestLen = len;
                result.clear();
                result.emplace_back(left, right);
            } else if( len > 0 && len == bestLen) {
                result.emplace_back(left, right);
            }
        }
    }

    for(auto res : result) {
        cout << res.first << ' ' << res.second << '\n';
    }
    return 0;
}