开始两个小时的思路全是错的，最后突然想到一种“水多了加面，面多了加水”那种类似的思路。
首先题目的意思是希望我们找到满足n个不应该递增的数组中至少存在一个数的最小范围。
然后我的思路就是先都成每个数组中最小的数开始（也就是数组中第一个数）；
记录一下最大和最小的一个，那么第一个满足条件的范围也就出来了，但它不一定是最小的；
那我们如何找到一个最小的满足条件的范围呢？
思考一下，是什么导致当前的范围大，很显然应该是边界值，也就是minn和maxx；
或者说，我们试着让minn所在的那个数组下标向前移动，那么minn一定会增大，也就可能导致范围变小。
然后再遍历一遍每个数组当前位置的值，再取最小，让这个数组下标向前移动。
直到导致某一个数组移动到最后一个位置，这个过程中一定能取到最小的范围。（这里我也不知道具体怎么解释，可能得读者自己思考一下）
这样也就诞生了我的第一版代码!
class Solution {
public:
vector<int> smallestRange(vector<vector<int>>& nums) {
int p[4000]={0},l=-1e9,r=1e9;
do
{
int minn=1e9,maxx=-1e9,k=-1;
for(int i=0;i<nums.size();i++)
{
if(nums[i][p[i]]<minn)
{
minn=nums[i][p[i]];
k=i;
}
maxx=max(nums[i][p[i]],maxx);
}
if(maxx-minn<r-l)
{
r=maxx;
l=minn;
}
if(++p[k]==nums[k].size()) break;
}while(1);
return {l,r};
}
};
罢特，有两个点超时了。
其实，聪明的你已经看出来了，上面的代码一副没有被算法洗礼过的丑陋模样，复杂度别提有多高了。
欸！我有一计，可破此局。因为刚好最近学到了djks，而刚好又对堆优化版本印象深刻。
所以直接想到了，这里也可以用堆优化!
代码如下
class Solution {
public:
#include<queue>
vector<int> smallestRange(vector<vector<int>>& nums) {
int p[4000]={0},l=-1e9,r=1e9,maxx=-1e9;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> heap;
for(int i=0;i<nums.size();i++)
{
heap.push({nums[i][p[i]],i});
maxx=max(nums[i][p[i]],maxx);
}
while(1)
{
auto x=heap.top();
heap.pop();
int minn=x.first,k=x.second;
if(maxx-minn<r-l)
{
r=maxx;
l=minn;
}
if(++p[k]<nums[k].size())
{
heap.push({nums[k][p[k]],k});
maxx=max(maxx,nums[k][p[k]]);
}
else break;
}
return {l,r};
}
};
这样最小值可以直接从小根堆里面取，不用把全部数组遍历一遍，每次找最小值的复杂度直接从n优化到logn。
写出来这题也是十分的爽啊！
啊啊啊啊啊啊啊啊啊啊啊
