Leetcode打卡：最小区间

执行结果：通过

题目：632 最小区间

你有 k 个 非递减排列 的整数列表。找到一个最小区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

示例 1：

输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出：[20,24]
解释： 
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

示例 2：

输入：nums = [[1,2,3],[1,2,3],[1,2,3]]
输出：[1,1]

提示：

nums.length == k
1 <= k <= 3500
1 <= nums[i].length <= 50
-105 <= nums[i][j] <= 105
nums[i] 按非递减顺序排列

代码以及解题思路

代码：

#define maxn 100005int heap[maxn];
int heap_count;
int **rec, *nx;bool heap_comp(int *first, int *second) {return rec[*first][nx[*first]] < rec[*second][nx[*second]];
}void swap(int *first, int *second) {int temp = *second;*second = *first;*first = temp;return;
}void push(int num) {int pos = ++heap_count;heap[pos] = num;while (pos > 1) {if (heap_comp(&heap[pos], &heap[pos >> 1])) {swap(&heap[pos], &heap[pos >> 1]);pos >>= 1;} elsebreak;}return;
}void pop() {int top_num = 1;int now;swap(&heap[top_num], &heap[heap_count--]);while ((now = (top_num << 1)) <= heap_count) {if (heap_comp(&heap[now + 1], &heap[now]) && now < heap_count) now++;if (heap_comp(&heap[now], &heap[top_num])) {swap(&heap[top_num], &heap[now]);top_num = now;} elsebreak;}
}int top() { return heap[1]; }int* smallestRange(int** nums, int numsSize, int* numsColSize, int* returnSize) {heap_count = 0;nx = (int *)malloc(sizeof(int) * numsSize);memset(nx, 0, sizeof(int) * numsSize);rec = nums;int rangeLeft = 0, rangeRight = 2147483647;int minValue = 0, maxValue = -2147483648;for (int i = 0; i < numsSize; ++i) {push(i);maxValue = fmax(maxValue, nums[i][0]);}while (true) {int row = top();pop();minValue = nums[row][nx[row]];if (maxValue - minValue < rangeRight - rangeLeft) {rangeLeft = minValue;rangeRight = maxValue;}if (nx[row] == numsColSize[row] - 1) {break;}++nx[row];maxValue = fmax(maxValue, nums[row][nx[row]]);push(row);}int *ret = malloc(sizeof(int) * 2);ret[0] = rangeLeft, ret[1] = rangeRight;*returnSize = 2;return ret;
}

解题思路：

数据结构准备

最小堆：使用数组 heap 来实现一个最小堆，堆中的元素是数组的索引。堆的大小由 heap_count 控制。
辅助数组：nx 数组用来记录每个数组当前考虑的元素的索引，rec 指向输入的二维数组。

堆的比较函数

heap_comp 函数：比较两个堆中元素（即数组索引）所指向的当前值的大小。这决定了堆的排序方式，即根据当前考虑的数组元素的值进行排序。

堆的基本操作

swap 函数：交换两个整数的值。
push 函数：将一个元素（数组索引）加入到堆中，并保持堆的性质。
pop 函数：移除堆顶元素，并重新调整堆以保持最小堆的性质。
top 函数：获取堆顶元素（不移除）。

主逻辑

初始化：
- 将所有数组的第一个元素加入堆中，并记录当前的最大值 maxValue。
- 初始化差值范围的左右边界 rangeLeft 和 rangeRight 为最大和最小可能的整数值。
迭代寻找最小差值范围：
- 从堆中取出当前最小值所在的数组索引 row。
- 更新当前的最小值 minValue。
- 检查当前的最小差值范围是否比已知的最小差值范围更小，如果是，则更新 rangeLeft 和 rangeRight。
- 如果当前数组的所有元素都已考虑过（即 nx[row] 指向数组的最后一个元素），则停止循环。
- 否则，移动到当前数组的下一个元素，更新 nx[row] 和 maxValue（如果需要的话）。
- 将当前数组索引重新加入堆中，以便在下一次迭代中考虑。
返回结果：
- 分配一个大小为2的整数数组 ret，用于存储最小差值范围的左右边界。
- 设置 *returnSize 为2，表示返回数组的大小。
- 返回 ret。