ZYF057 最小区间
大约 5 分钟
ZYF057 最小区间
【算法】 贪心、双指针、排序、滑动窗口
【C++】 数组、sort、结构体
【难度】普及−
一、题目简述
给定 个非递减排列(即已从小到大排好序)的整数数组。要求找出一个最小区间 ,使得这 个数组中,每个数组都至少有一个数落在 区间内。
"最小"的定义是:先比较区间长度 ,长度越短越好;长度相同时比较左端点 , 越小越好。
数据范围(本题数据较小时可暴力,但需掌握正解):
| 变量 | 范围 |
|---|---|
| (数组个数) | |
| 每个数组长度 | |
| 元素值 | |
| 总元素个数 |
二、解题思路
2.1 问题转化
题目要求从每个数组中至少选一个数,使得这些数的最大值与最小值之差最小。
想象把所有 个数组的元素全部混在一起,按数值从小到大排序。那么我们只需要在这个大序列上找一个连续的区间(称为"滑动窗口"),使得窗口内至少包含来自每个数组的元素各一个,然后取窗口两端点值之差最小的那个即可。
2.2 为什么贪心+滑动窗口可行?
关键观察:如果我们在排好序的序列上滑动窗口:
- 窗口右端点 不断向右扩展,把新元素"收入"窗口
- 当窗口覆盖了全部 个数组后,尝试从左边缩窄窗口(左端点 右移)
- 每次缩窄前,当前窗口对应的区间 就是一个候选答案
- 因为序列已排序,窗口左右端点的值就是区间的最小值和最大值,区间长度就是
这样我们可以枚举所有"能覆盖全部 个数组"的极小窗口,从中选出最优的。
2.3 手动模拟
以样例 1 为例:
k = 3
数组1: [4, 10, 15, 24, 26]
数组2: [0, 9, 12, 20]
数组3: [5, 18, 22, 30]将所有元素标记来源后排序:
值: 0 4 5 9 10 12 15 18 20 22 24 26 30
来源: 2 1 3 2 1 2 1 3 2 3 1 1 3滑动窗口过程(关键几步):
| 步骤 | 窗口范围 | 覆盖数组 | 区间 | 长度 |
|---|---|---|---|---|
| 初态 | [0, 4, 5] | {1,2,3} ✓ | [0, 5] | 5 |
| 缩左 | [4, 5] | {1,3} ✗ | — | — |
| 扩展 | [4, 5, 9] | {1,2,3} ✓ | [4, 9] | 5 |
| ... | ... | ... | ... | ... |
| 某步 | [20, 22, 24] | {1,2,3} ✓ | [20, 24] | 4 ✓ |
最终最优区间为 ,长度为 4。
2.4 算法步骤
- 读入并标记:用一个结构体数组存所有
(数值, 来自第几个数组)的对 - 排序:按数值从小到大排序
- 滑动窗口:
- 维护
cnt[i]:当前窗口内来自第 个数组的元素个数 - 维护
cover:当前窗口覆盖了几个不同的数组 - 右移时,
cnt[idx]++,若从 0 变 1 则cover++ - 当
cover == k时,不断尝试右移 (缩窄窗口),更新答案,直到cover < k
- 维护
- 输出答案
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5; // 总元素上限 3500×50 = 175000
const int K = 3505; // 数组个数上限
struct Node {
int val; // 元素的值
int idx; // 来自第几个数组(1-based)
} a[N];
int cnt[K]; // cnt[i]: 窗口内第i个数组的元素个数
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
cin >> k;
// 1. 读入所有元素,标记来源
int tot = 0;
for (int i = 1; i <= k; i++) {
int n;
cin >> n;
for (int j = 1; j <= n; j++) {
int x;
cin >> x;
a[++tot] = {x, i};
}
}
// 2. 按数值排序
sort(a + 1, a + tot + 1, [](Node x, Node y) {
return x.val < y.val;
});
// 3. 滑动窗口
int l = 1; // 窗口左端点
int cover = 0; // 当前覆盖了几个数组
int ansL = a[1].val; // 答案左端点
int ansR = a[tot].val; // 答案右端点(初始化为整个范围)
for (int r = 1; r <= tot; r++) {
// 右端点扩展:收入 a[r]
if (cnt[a[r].idx] == 0) cover++;
cnt[a[r].idx]++;
// 当窗口覆盖了全部 k 个数组,尝试缩窄左端点
while (cover == k) {
// 更新答案
int curLen = a[r].val - a[l].val;
int ansLen = ansR - ansL;
if (curLen < ansLen) {
ansL = a[l].val;
ansR = a[r].val;
}
// 左端点右移:丢掉 a[l]
cnt[a[l].idx]--;
if (cnt[a[l].idx] == 0) cover--;
l++;
}
}
cout << ansL << " " << ansR << endl;
return 0;
}四、复杂度分析
- 时间复杂度:,其中 是所有元素的总个数()。排序占主导 ,滑动窗口阶段每个元素恰好被左指针和右指针各访问一次,为 。在本题数据范围内可以轻松通过。
- 空间复杂度:,结构体数组 占用 ,计数数组
cnt占用 。
五、知识扩展
5.1 另一种解法:最小堆(多路归并)
这题还有一个经典的堆解法(类似合并 K 个有序链表):
- 把每个数组的第一个元素放入一个小根堆
- 记录堆中当前最大值
curMax - 每次弹出堆顶(当前最小值),用
curMax - minVal更新答案 - 从弹出元素所属的数组中取下一个元素加入堆,更新
curMax - 重复直到某个数组用完
堆解法的时间复杂度是 ,在 很大时比排序法更优。但对于 CSP-J 阶段,滑动窗口法更直观易懂。
5.2 易错点
- 排序时只按数值排序即可,不需要考虑来源
- 答案的初始值应该设为 (整个值域),不能设为
- 滑动窗口缩窄时,要先更新答案再移动左指针,否则会漏掉当前窗口
cnt数组要开到 的大小(静态数组),本题
5.3 类似题目
- LeetCode 632. 最小区间(Smallest Range Covering Elements from K Lists)—— 本题原题
- 洛谷 P1631 序列合并 —— 类似的多路归并思想
