C++算法题-C++代码：冬季暖系统温度稳定性分析

题目重述

我们需要分析一个小区冬季采暖系统的温度稳定性。具体规则如下：

• 采样了 n 次室内温度，按顺序记录。
• 恒温服务承诺：
  • 室内温度保持在 [18, 24] 摄氏度之间。
  • 温差（最大温度 - 最小温度）不超过 4 摄氏度。
• 我们需要找到所有满足上述条件的连续子数组（区间），并从中找出最长的那些区间。
• 如果有多个最长区间，按起始索引升序输出它们的起始和结束索引（从 0 开始）。

样例分析

样例输入：

6
16 18 20 25 23 20

解释：

• 温度序列：[16, 18, 20, 25, 23, 20]
• 索引：0, 1, 2, 3, 4, 5

检查所有可能的连续子区间：

• [16]：16 ∉ [18,24]，不满足。
• [18]：18 ∈ [18,24]，温差为 0，满足。
• [20]：20 ∈ [18,24]，温差为 0，满足。
• [25]：25 ∉ [18,24]，不满足。
• [23]：23 ∈ [18,24]，温差为 0，满足。
• [20]：20 ∈ [18,24]，温差为 0，满足。
• [16,18]：16 ∉ [18,24]，不满足。
• [18,20]：18,20 ∈ [18,24]，温差 20-18=2 ≤4，满足。
• [20,25]：25 ∉ [18,24]，不满足。
• [25,23]：25 ∉ [18,24]，不满足。
• [23,20]：23,20 ∈ [18,24]，温差 23-20=3 ≤4，满足。
• [16,18,20]：16 ∉ [18,24]，不满足。
• [18,20,25]：25 ∉ [18,24]，不满足。
• [20,25,23]：25 ∉ [18,24]，不满足。
• [25,23,20]：25 ∉ [18,24]，不满足。
• 更长区间同理不满足。

满足条件的区间：

• [18]：起始 1，结束 1，长度 1
• [20]：起始 2，结束 2，长度 1
• [23]：起始 4，结束 4，长度 1
• [20]：起始 5，结束 5，长度 1
• [18,20]：起始 1，结束 2，长度 2
• [23,20]：起始 4，结束 5，长度 2

最长长度为 2，对应的区间：

• [1,2]
• [4,5]

解题思路

1. 滑动窗口：我们需要找到所有满足条件的连续子数组。可以使用滑动窗口（双指针）技术。
2. 窗口条件：
   • 窗口内所有温度 ∈ [18,24]。
   • 窗口内最大温度 - 最小温度 ≤ 4。
3. 维护窗口：
   • 使用双指针 left 和 right 表示当前窗口。
   • 使用两个单调队列（或类似结构）维护窗口内的最小值和最大值，以便快速计算温差。
   • 如果当前窗口不满足条件，移动 left 指针缩小窗口。
4. 记录满足条件的窗口：
   • 每次窗口满足条件时，记录其长度和起始/结束索引。
   • 最后在所有记录中找出最长的那些窗口，并按起始索引升序输出。

C++实现

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

using namespace std;

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

    vector<pair<int, int>> valid_intervals; // {start, end}
    deque<int> min_q, max_q; // 单调队列，min_q维护最小值，max_q维护最大值
    int left = 0;

    for (int right = 0; right < n; ++right) {
        int current = temps[right];

        // 如果当前温度不在[18,24]，重置窗口
        if (current < 18 || current > 24) {
            left = right + 1;
            min_q.clear();
            max_q.clear();
            continue;
        }

        // 维护min_q（递增队列）
        while (!min_q.empty() && temps[min_q.back()] >= current) {
            min_q.pop_back();
        }
        min_q.push_back(right);

        // 维护max_q（递减队列）
        while (!max_q.empty() && temps[max_q.back()] <= current) {
            max_q.pop_back();
        }
        max_q.push_back(right);

        // 检查窗口是否满足温差<=4
        while (left <= right) {
            int current_min = temps[min_q.front()];
            int current_max = temps[max_q.front()];
            if (current_max - current_min > 4) {
                left++;
                // 移除left左侧的元素
                while (!min_q.empty() && min_q.front() < left) {
                    min_q.pop_front();
                }
                while (!max_q.empty() && max_q.front() < left) {
                    max_q.pop_front();
                }
            } else {
                break;
            }
        }

        // 记录满足条件的区间
        if (left <= right) {
            valid_intervals.emplace_back(left, right);
        }
    }

    // 找出最长的区间
    int max_len = 0;
    for (const auto& interval : valid_intervals) {
        int len = interval.second - interval.first + 1;
        if (len > max_len) {
            max_len = len;
        }
    }

    // 收集所有最长区间
    vector<pair<int, int>> result;
    for (const auto& interval : valid_intervals) {
        int len = interval.second - interval.first + 1;
        if (len == max_len) {
            result.push_back(interval);
        }
    }

    // 去重并排序（可能有重叠或相同的区间）
    sort(result.begin(), result.end());
    result.erase(unique(result.begin(), result.end()), result.end());

    // 输出
    for (const auto& interval : result) {
        cout << interval.first << " " << interval.second << endl;
    }

    return 0;
}

代码解释

1. 输入处理：读取温度采样次数和温度序列。
2. 滑动窗口：
   • 使用双指针 left 和 right 维护当前窗口。
   • 使用单调队列 min_q 和 max_q 分别维护窗口内的最小值和最大值，以便快速计算温差。
3. 窗口条件检查：
   • 如果当前温度不在 [18,24]，重置窗口。
   • 如果温差超过 4，移动 left 缩小窗口。
4. 记录和输出：
   • 记录所有满足条件的区间。
   • 找出最长区间并去重排序后输出。

测试样例

输入：

6
16 18 20 25 23 20

输出：

1 2
4 5

与样例一致。