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

15303105423

一、题目解读

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

二、解题思路

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

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

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

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

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

三、解题步骤

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

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

3. 循环：

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

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

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

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

四、代码与注释

1. #include <iostream>
   
2. #include <vector>
   
3. #include <queue>
   
4. #include <climits>
   
5. using namespace std;
   
6. 
   
7. struct Element {
   
8.     int val;    // 元素值
   
9.     int row;    // 所属数组索引
   
10.     int col;    // 在数组中的位置
    
11.    
    
12.     bool operator>(const Element& other) const {
    
13.         return val > other.val;
    
14.     }
    
15. };
    
16. 
    
17. vector<int> smallestRange(vector<vector<int>>& nums) {
    
18.     int k = nums.size();
    
19.     priority_queue<Element, vector<Element>, greater<Element>> min_heap;
    
20.    
    
21.     int current_max = INT_MIN;
    
22.     // 初始化堆，放入每个数组的第一个元素
    
23.     for (int i = 0; i < k; ++i) {
    
24.         min_heap.push({nums[i][0], i, 0});
    
25.         current_max = max(current_max, nums[i][0]);
    
26.     }
    
27.    
    
28.     int range_start = 0, range_end = INT_MAX;
    
29.    
    
30.     while (true) {
    
31.         Element min_element = min_heap.top();
    
32.         min_heap.pop();
    
33.         
    
34.         // 更新最小区间
    
35.         if (current_max - min_element.val < range_end - range_start) {
    
36.             range_start = min_element.val;
    
37.             range_end = current_max;
    
38.         } else if (current_max - min_element.val == range_end - range_start &&
    
39.                   min_element.val < range_start) {
    
40.             range_start = min_element.val;
    
41.             range_end = current_max;
    
42.         }
    
43.         
    
44.         // 如果某个数组已经遍历完，结束循环
    
45.         if (min_element.col + 1 == nums[min_element.row].size()) {
    
46.             break;
    
47.         }
    
48.         
    
49.         // 将当前数组的下一个元素加入堆
    
50.         int next_val = nums[min_element.row][min_element.col + 1];
    
51.         min_heap.push({next_val, min_element.row, min_element.col + 1});
    
52.         current_max = max(current_max, next_val);
    
53.     }
    
54.    
    
55.     return {range_start, range_end};
    
56. }
    
57. 
    
58. int main() {
    
59.     int k, n;
    
60.     cin >> k >> n;
    
61.    
    
62.     vector<vector<int>> nums(k, vector<int>(n));
    
63.     for (int i = 0; i < k; ++i) {
    
64.         for (int j = 0; j < n; ++j) {
    
65.             cin >> nums[i][j];
    
66.         }
    
67.     }
    
68.    
    
69.     vector<int> result = smallestRange(nums);
    
70.     cout << result[0] << " " << result[1] << endl;
    
71.    
    
72.     return 0;
    
73. }

复制代码

五、总结

本解法核心在于利用优先队列维护多数组元素的有序性，通过滑动窗口动态调整区间范围，避免了暴力遍历所有组合。时间复杂度为O(NlogK)（N为总元素数，K为数组数量），空间复杂度为O(K)。通过优化区间更新逻辑，确保在相等长度时优先选择更小区间，从而准确求解最小范围。

来源：牛客网题解