)
最小请求间隔限流策略
2026 华为OD机试真题 5月24日华为OD上机新系统考试真题 100 分题型
点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解
题目描述
在微服务网关中，为了防止某个用户短时间内发送过多请求，通常会采用最小请求间隔限流策略：即同一个用户相邻两个请求的时间戳之差必须大于等于 minInterval 秒。例如，若 minInterval=2，则请求时间戳为 1 和 3 可以同时通过（差为 2），但 1 和 2 不能同时通过（差为 1）。
现有一批属于同一用户的请求，每个请求带有一个时间戳（单位：秒，整数）。网关需要从这批请求中挑选一部分放行，使得任意两个被放行的请求时间差都 ≥minInterval。请你计算一共有多少种合法的放行方案（包括空集）。
例如，请求时间戳为 [1,3,4]，minInterval=2，则合法的放行方案有：[]、[1]、[3]、[4]、[1,3]、[1,4]，共6种（注意 [3,4] 非法，因为差为 1<2）。
2026 华为OD机试真题 5月24日华为OD上机新系统考试真题 100 分题型
输入描述
- int[] timestamps：整数数组，表示每个请求的时间戳（可能乱序，无重复）。
- int minInterval：最小允许的请求间隔（秒），minInterval≥1。
输出描述
- int：合法放行方案的总数。
数据规模
- 1≤timestamps.length≤15
- 时间戳取值范围：0≤timestamp≤109
- minInterval 为正整数
示例1
输入
[1,2,4],2输出
6说明
合法方案：[]、[1]、[2]、[4]、[1,4]、[2,4]，共 6 种
示例2
输入
[10],5输出
2说明
合法方案：[]、[10]，共 2 种
解题思路
核心思想
本题的核心在于枚举所有可能的放行方案，并验证其合法性。
关键观察：1. 给定 n 个请求时间戳 (1 ≤ n ≤ 15)，我们可以枚举所有可能的放行子集 2. 对于每个子集，需要验证任意两个被选中的时间戳之间的间隔都 ≥ minInterval 3. 由于 n ≤ 15，最多有 2^15 = 32768 个子集，直接枚举完全可行
算法步骤
排序处理：将时间戳数组按升序排列。排序后，间隔问题变得更容易处理。
位掩码枚举：使用 0 到 (1 << n) - 1 的整数作为掩码，其中： - 第 i 位为 1 表示选择第 i 个时间戳 - 第 i 位为 0 表示不选择第 i 个时间戳
合法性检查：对于每个掩码表示的方案，检查任意两对被选中时间戳的间隔是否都 ≥ minInterval。
计数统计：统计所有合法方案的数量。
复杂度分析
- 时间复杂度：O(n × 2^n)
- 共有 2^n 个子集
- 对每个子集需要 O(n²) 的时间检查间隔
由于 n ≤ 15，32768 × 225 ≈ 740万次操作，可接受
空间复杂度：O(n)
- 主要用于存储排序后的时间戳和临时选中的子集
正确性证明
定理：算法返回的计数等于所有满足最小间隔约束的放行方案数量。
证明： 1.完备性：算法遍历了所有 2^n 个可能的放行方案（包括空集），因为每个请求有"放行"或"不放行"两种状态。
正确性检查：对于每个方案，算法检查所有任意两对时间戳 (i, j)，确保 timestamps[j] - timestamps[i] ≥ minInterval。由于时间戳已排序，只需检查相邻元素即可。
计数准确：只有通过合法性检查的方案才会被计入答案，因此最终计数恰好是合法方案的数量。
**Q.E.