632.最小區間

題解

class Solution {
    class NumGroup{
        public NumGroup(int num, int grp){
            this.num = num;
            this.grp = grp;
        }
        int num; //數值
        int grp; //組号
    }
    public int[] smallestRange(List<List<Integer>> nums) {
        //因為每次都要找最小元素，是以維護一個最小堆比較合适
        PriorityQueue<NumGroup> numgrp = new PriorityQueue<>(new Comparator<NumGroup>(){
            @Override 
            public int compare(NumGroup n1, NumGroup n2){
                return n1.num - n2.num;
            }
        });

        int end = -100001;
        //記錄每個數組目前的指針位置，一開始都指向第0個元素，即每個區間的最小元素
        int[] index = new int[nums.size()];

        //起始區間
        for(int i = 0; i < nums.size(); i++){
            if(nums.get(i).get(0) > end) end = nums.get(i).get(0);
            NumGroup num = new NumGroup(nums.get(i).get(0), i);
            numgrp.offer(num);
        }

        int max = end;
        int start = numgrp.peek().num;
        int min = start;
        int len = end - start + 1;

        while(true){
            //grp為目前最小元素的原數組号
            int grp = numgrp.poll().grp;
            //如果目前最小元素已經是原數組最大元素了，則退出
            if(index[grp]+1 == nums.get(grp).size()) break;

            //索引++，并将目前最小元素的原數組中的下一個元素壓入優先級隊列
            index[grp]++;
            NumGroup n = new NumGroup(nums.get(grp).get(index[grp]), grp);
            numgrp.offer(n);
            //目前最大值
            if(n.num > max) max = n.num;
            min = numgrp.peek().num;
            //長度變小
            if(max-min+1 < len){
                start = min;
                end = max;
                len = max-min+1;
            }
        }

        return new int[]{start, end};
    }
}