JAVA程序设计：最小区间（LeetCode：632）

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

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

示例 1:

输入:[[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] 中。

注意:

给定的列表可能包含重复元素，所以在这里升序表示 >= 。

1 <= k <= 3500

-105 <= 元素的值 <= 105

对于使用Java的用户，请注意传入类型已修改为List<List<Integer>>。重置代码模板后可以看到这项改动。

思路：不知道我的方法是不是最优的，耗时不算多。我的具体做法是开k个指针，表示每个列表已经算到哪个点了，我们知道为了让区间最小，肯定是让数越接近越好，我们可以维护一个小顶堆，这个堆里有且只有k个数，并且这k个数是属于不同的列表里的，任意两个都不会来自同一个列表。我想很多人读到这里应该能明白我到底要干什么，我这个小顶堆队头肯定是当前能包含堆里k个数的做区间，而队尾就是右区间啦。更新堆的条件让堆顶弹出并且让堆顶的元素所属的列表的下一个元素入堆，然后更新区间。

class Solution {
	
	class node implements Comparable<node>{
		int x,y;
		public node(int x,int y) {
			this.x=x;
			this.y=y;
		}
		@Override
		public int compareTo(node o) {
			// TODO 自动生成的方法存根
			if(x==o.x) return y-o.y;
			return x-o.x;
		}
		
	}
	
    public int[] smallestRange(List<List<Integer>> nums) {
        
    	int[] ans=new int[2];
    	int[] index=new int[nums.size()];
        PriorityQueue<node> q=new PriorityQueue<>();
        
        int mins=Integer.MAX_VALUE;
        int maxs=Integer.MIN_VALUE;
        
        for(int i=0;i<nums.size();i++) {
        	mins=Math.min(mins, nums.get(i).get(0));
        	maxs=Math.max(maxs, nums.get(i).get(0));
        	q.add(new node(nums.get(i).get(0),i));
        	index[i]++;
        }
        
        ans[0]=mins; ans[1]=maxs;
        
        while(true) {
        	boolean flag=false;
        	for(int i=0;i<nums.size();i++) {
        		if(index[i]==nums.get(i).size()) continue;
        		int tmp=nums.get(i).get(index[i]);
        		if(tmp>=mins && tmp<=maxs && q.peek().x<=tmp && q.peek().y==i) {
        			flag=true;
        			q.poll(); q.add(new node(tmp,i));
        			mins=Math.max(mins, q.peek().x);
        			if(maxs-mins+1<ans[1]-ans[0]+1) {
        				ans[0]=mins;
        				ans[1]=maxs;
        			}
        			index[i]++;
        		}
        		if(!flag) {
        			int p=q.peek().y;
        			if(index[p]<nums.get(p).size()) {
        				q.poll();
        				q.add(new node(nums.get(p).get(index[p]),p));
        				index[p]++;
        				flag=true;
        				mins=Math.max(mins, q.peek().x);
        				maxs=Math.max(maxs, nums.get(p).get(index[p]-1));
            			if(maxs-mins+1<ans[1]-ans[0]+1) {
            				ans[0]=mins;
            				ans[1]=maxs;
            			}
        			}
        			else break;
        		}
        	}
        	if(!flag) break;
        }
        return ans;
    }
}