当前位置：首页 > 牛客 > 牛客17799题：滑动窗口+优先队列解决多数组最小区间

牛客17799题：滑动窗口+优先队列解决多数组最小区间

1个月前 (08-06)

一、题目解读

牛客17799题要求在一个由K个有序数组组成的集合中，找到包含所有数组元素的最小区间范围。即需确定一个区间[range_start, range_end]，使得每个数组中至少有一个元素落在该区间内，且区间长度最小。题目考验对多数组合并与区间优化的处理能力。

二、解题思路

采用“滑动窗口+优先队列”策略：

1. 初始化：将每个数组的首元素加入小根堆（优先队列），记录当前堆顶元素（最小值）与最大值。

2. 滑动窗口：每次取出堆顶元素（当前窗口最小值），更新区间范围。若该元素所在数组存在后续元素，则将其加入堆并更新最大值。

3. 循环终止条件：当某个数组的所有元素已被遍历时结束，确保每个数组至少贡献一个元素到区间。

4. 区间更新逻辑：通过比较新旧区间的长度和起始值，动态维护最小范围。

三、解题步骤

1. 创建包含元素值、行索引、列索引的结构体，重载运算符支持优先队列排序。

2. 初始化堆：遍历K个数组首元素，加入堆并记录当前最大值。

3. 循环：

○ 弹出堆顶元素，更新区间范围（根据差值或起始值优先级）。

○ 若该元素非所在数组末尾，则将其下一元素加入堆并更新最大值。

○ 若某数组遍历完毕，终止循环。

4. 返回最终区间[range_start, range_end]。

四、代码与注释

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

struct Element {
    int val;    // 元素值
    int row;    // 所属数组索引
    int col;    // 在数组中的位置
    
    bool operator>(const Element& other) const {
        return val > other.val;
    }
};

vector<int> smallestRange(vector<vector<int>>& nums) {
    int k = nums.size();
    priority_queue<Element, vector<Element>, greater<Element>> min_heap;
    
    int current_max = INT_MIN;
    // 初始化堆，放入每个数组的第一个元素
    for (int i = 0; i < k; ++i) {
        min_heap.push({nums[i][0], i, 0});
        current_max = max(current_max, nums[i][0]);
    }
    
    int range_start = 0, range_end = INT_MAX;
    
    while (true) {
        Element min_element = min_heap.top();
        min_heap.pop();
        
        // 更新最小区间
        if (current_max - min_element.val < range_end - range_start) {
            range_start = min_element.val;
            range_end = current_max;
        } else if (current_max - min_element.val == range_end - range_start && 
                  min_element.val < range_start) {
            range_start = min_element.val;
            range_end = current_max;
        }
        
        // 如果某个数组已经遍历完，结束循环
        if (min_element.col + 1 == nums[min_element.row].size()) {
            break;
        }
        
        // 将当前数组的下一个元素加入堆
        int next_val = nums[min_element.row][min_element.col + 1];
        min_heap.push({next_val, min_element.row, min_element.col + 1});
        current_max = max(current_max, next_val);
    }
    
    return {range_start, range_end};
}

int main() {
    int k, n;
    cin >> k >> n;
    
    vector<vector<int>> nums(k, vector<int>(n));
    for (int i = 0; i < k; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> nums[i][j];
        }
    }
    
    vector<int> result = smallestRange(nums);
    cout << result[0] << " " << result[1] << endl;
    
    return 0;
}