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

火星探测器稳定性分析

https://www.nowcoder.com/practice/3917b4936f5b4261be0cef13f957bc43

题目链接

火星探测器稳定性分析

题目描述

“祝融号”火星探测器为了保证仪器的正常运行和数据的准确性，必须满足以下两个条件：

仪器的“环境稳定性指数” $S$ 必须维持在 $[18, 24]$ 的区间内，即 $18 \le S \le 24$ 。
在任何一次连续的工作期间内，环境稳定性指数的最大波动范围（即该期间的 $S_{max} - S_{min}$ ）不得超过 $4$ ，即 $S_{max} - S_{min} \le 4$ 。

现在，探测器采集了 $N$ 次环境稳定性指数。为了最大化单次有效工作时长，请你找出满足上述两个稳定条件的、持续时间最长的一个或多个时间段。

输入:

第一行包含一个整数 $N$ 。
第二行包含 $N$ 个整数，表示按顺序采集的环境稳定性指数。

输出:

输出持续时间最长且满足稳定条件的时间段的起始索引和结束索引。如果存在多个这样的时间段，按起始索引升序逐行输出。

解题思路

本题要求解的是满足特定条件的最长连续子数组。由于数据规模 $N$ 可达 $10^5$ ， $\mathcal{O}(N^2)$ 的暴力解法会超时，因此我们需要一个更高效的算法。本题是滑动窗口算法的典型应用场景，时间复杂度可以优化到 $\mathcal{O}(N)$ 。

首先，题目有两个条件：

范围条件：子数组中所有元素 $S$ 都必须在 $[18, 24]$ 范围内。
波动条件：子数组中的最大值与最小值之差 $S_{max} - S_{min}$ 不能超过 $4$ 。

不满足范围条件的元素不可能存在于任何有效的时间段内。因此，这些元素自然地将整个数据序列分成了若干个连续的子段，我们只需要在这些子段内部寻找满足波动条件的最长区间即可。

算法步骤如下：

初始化最长长度 $max\_len = 0$ 和结果列表 $results$ 。
遍历整个数据序列，以不满足范围条件的元素或序列末尾为界，将序列划分为多个只包含满足范围条件元素的子段。
对每一个子段，我们使用滑动窗口来寻找满足波动条件的最长部分： a. 维护一个窗口的左右边界 $left$ 和 $right$ 。 $left$ 初始为子段的起始位置。 b. 维护两个双端队列（deque）：一个单调递增队列 $min\_dq$ 用于快速获取窗口内的最小值，一个单调递减队列 $max\_dq$ 用于获取窗口内的最大值。队列中存储的是元素的索引。 c. 移动右边界 $right$ ，不断扩大窗口。每加入一个新元素 $data[right]$ ： i. 更新 $min\_dq$ ：从队尾移除所有值大于等于 $data[right]$ 的元素，然后将 $right$ 入队。 ii. 更新 $max\_dq$ ：从队尾移除所有值小于等于 $data[right]$ 的元素，然后将 $right$ 入队。 d. 检查波动条件：此时窗口内的最大值是 $data[max\_dq.front()]$ ，最小值是 $data[min\_dq.front()]$ 。如果它们的差大于 $4$ ，说明窗口不再有效，需要收缩左边界。 e. 收缩左边界 $left$ ： i. 如果 $min\_dq$ 或 $max\_dq$ 的队首索引等于 $left$ ，说明窗口的最值即将被移出，将其出队。 ii. 将 $left$ 右移一位。 iii. 重复此过程，直到窗口再次满足波动条件。 f. 每次窗口调整后，它都是一个有效的区间。计算当前窗口长度 $right - left + 1$ ，并与 $max\_len$ 比较，更新 $max\_len$ 和 $results$ 列表。
在处理完所有子段后， $results$ 中存储的就是最终答案。

这种方法保证每个元素最多只入队和出队一次，因此对每个子段的处理是线性的。总体时间复杂度为 $\mathcal{O}(N)$ 。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

// 用于处理一个子段的滑动窗口函数
void process_segment(int start, int end, const vector<int>& data, int& max_len, vector<pair<int, int>>& results) {
    if (start > end) {
        return;
    }
    deque<int> min_dq, max_dq;
    int left = start;

    for (int right = start; right <= end; ++right) {
        // 维护单调递增队列(队首最小)
        while (!min_dq.empty() && data[min_dq.back()] >= data[right]) {
            min_dq.pop_back();
        }
        min_dq.push_back(right);

        // 维护单调递减队列(队首最大)
        while (!max_dq.empty() && data[max_dq.back()] <= data[right]) {
            max_dq.pop_back();
        }
        max_dq.push_back(right);

        // 如果窗口内极差大于4，收缩左边界
        while (data[max_dq.front()] - data[min_dq.front()] > 4) {
            if (min_dq.front() == left) {
                min_dq.pop_front();
            }
            if (max_dq.front() == left) {
                max_dq.pop_front();
            }
            left++;
        }

        // 检查并更新最长长度
        int current_len = right - left + 1;
        if (current_len > max_len) {
            max_len = current_len;
            results.clear();
            results.push_back({left, right});
        } else if (current_len == max_len) {
            results.push_back({left, right});
        }
    }
}

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

    int max_len = 0;
    vector<pair<int, int>> results;
    int T_MIN = 18, T_MAX = 24;

    int segment_start = 0;
    for (int i = 0; i < n; ++i) {
        if (data[i] < T_MIN || data[i] > T_MAX) {
            // 遇到不合格数据，处理前一个段
            process_segment(segment_start, i - 1, data, max_len, results);
            // 新段的起点是下一个位置
            segment_start = i + 1;
        }
    }
    // 处理最后一个段
    process_segment(segment_start, n - 1, data, max_len, results);

    if (max_len == 0 && !results.empty()){
        // 如果有结果但长度为0，说明最长的是单个元素
        // 这种情况在process_segment中已经处理，但为了逻辑完备
    } else if (results.empty()){
        // 如果没有找到任何符合条件的段
        // 题目要求输出最长时间段，若一个都没有，则不输出
    }


    for (const auto& p : results) {
        cout << p.first << " " << p.second << "\n";
    }

    return 0;
}

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int max_len = 0;
    static List<int[]> results = new ArrayList<>();
    static final int T_MIN = 18;
    static final int T_MAX = 24;
    static final int M = 4;

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

        int segment_start = 0;
        for (int i = 0; i < n; i++) {
            if (data[i] < T_MIN || data[i] > T_MAX) {
                // 遇到不合格数据，处理前一个段
                processSegment(segment_start, i - 1, data);
                // 新段的起点是下一个位置
                segment_start = i + 1;
            }
        }
        // 处理最后一个段
        processSegment(segment_start, n - 1, data);

        for (int[] res : results) {
            System.out.println(res[0] + " " + res[1]);
        }
    }
    
    // 用于处理一个子段的滑动窗口方法
    private static void processSegment(int start, int end, int[] data) {
        if (start > end) {
            return;
        }
        LinkedList<Integer> minDq = new LinkedList<>();
        LinkedList<Integer> maxDq = new LinkedList<>();
        int left = start;

        for (int right = start; right <= end; right++) {
            // 维护单调递增队列(队首最小)
            while (!minDq.isEmpty() && data[minDq.peekLast()] >= data[right]) {
                minDq.pollLast();
            }
            minDq.addLast(right);

            // 维护单调递减队列(队首最大)
            while (!maxDq.isEmpty() && data[maxDq.peekLast()] <= data[right]) {
                maxDq.pollLast();
            }
            maxDq.addLast(right);

            // 如果窗口内极差大于M，收缩左边界
            while (data[maxDq.peekFirst()] - data[minDq.peekFirst()] > M) {
                if (minDq.peekFirst() == left) {
                    minDq.pollFirst();
                }
                if (maxDq.peekFirst() == left) {
                    maxDq.pollFirst();
                }
                left++;
            }

            // 检查并更新最长长度
            int current_len = right - left + 1;
            if (current_len > max_len) {
                max_len = current_len;
                results.clear();
                results.add(new int[]{left, right});
            } else if (current_len == max_len) {
                results.add(new int[]{left, right});
            }
        }
    }
}

from collections import deque

def process_segment(start, end, data, max_len_info, results):
    if start > end:
        return
    
    min_dq, max_dq = deque(), deque()
    left = start
    
    for right in range(start, end + 1):
        # 维护单调递增队列(队首最小)
        while min_dq and data[min_dq[-1]] >= data[right]:
            min_dq.pop()
        min_dq.append(right)
        
        # 维护单调递减队列(队首最大)
        while max_dq and data[max_dq[-1]] <= data[right]:
            max_dq.pop()
        max_dq.append(right)
        
        # 如果窗口内极差大于4，收缩左边界
        while data[max_dq[0]] - data[min_dq[0]] > 4:
            if min_dq[0] == left:
                min_dq.popleft()
            if max_dq[0] == left:
                max_dq.popleft()
            left += 1
            
        # 检查并更新最长长度
        current_len = right - left + 1
        if current_len > max_len_info[0]:
            max_len_info[0] = current_len
            results.clear()
            results.append((left, right))
        elif current_len == max_len_info[0]:
            results.append((left, right))

# 读取输入
n = int(input())
data = list(map(int, input().split()))

T_MIN, T_MAX = 18, 24
max_len_info = [0] # 使用列表来传递可变对象
results = []

segment_start = 0
for i in range(n):
    if not (T_MIN <= data[i] <= T_MAX):
        # 遇到不合格数据，处理前一个段
        process_segment(segment_start, i - 1, data, max_len_info, results)
        # 新段的起点是下一个位置
        segment_start = i + 1

# 处理最后一个段
process_segment(segment_start, n - 1, data, max_len_info, results)

for res in results:
    print(res[0], res[1])

算法及复杂度

算法：分段 + 滑动窗口（双端队列优化）
时间复杂度： $\mathcal{O}(N)$ ，其中 $N$ 是采集数据的次数。我们只需要一次遍历来划分段落，滑动窗口算法保证每个元素最多进出双端队列一次，所以总体是线性的。
空间复杂度： $\mathcal{O}(W)$ ，其中 $W$ 是滑动窗口的最大尺寸。在最坏情况下， $W$ 可能等于 $N$ ，所以空间复杂度为 $\mathcal{O}(N)$ 。