力扣632.最小区间
-
贪心 + 最小堆
- 用一个小根堆维护K个数
- 其中最小的算完结果后弹出,再补一个进去
-
class Solution {public:vector<int> smallestRange(vector<vector<int>>& nums) {int l=0,r=INT_MAX;int n = nums.size();//记录下一个位置的下标vector<int> next(n);//按照数值排序auto cmp = [&](const int &u,const int &v){return nums[u][next[u]] > nums[v][next[v]];};//priority_queue<int,vector<int>,decltype(cmp)> pq(cmp);//当前的上下限int minval = 0,maxval = INT_MIN;//把所有列表放进去for(int i=0;i<n;i++){pq.emplace(i);maxval = max(maxval,nums[i][0]);}while(true){//最小数的下标int row = pq.top();pq.pop();minval = nums[row][next[row]];//更优if(maxval - minval < r - l)l = minval , r = maxval;//当前列表全部遍历过了if(next[row] == nums[row].size() - 1)break;//next往后移动一位next[row] ++;//更新当前k个数中最大值maxval = max(maxval,nums[row][next[row]]);pq.emplace(row);}return {l,r};}};