leetcode题解 632. Smallest Range

原题：https://leetcode.com/problems/smallest-range/#/description 题意：找到一个范围，可以存在n个list都有数在这个范围内

思路：类似于merge多个有序数组，用heap存储n个数，每个List一个，然后每次poll，找出最小的数，并安排该List加入新的元素，然后用max - min，找出范围，最后给出最小的范围，就是类似于归并排序中的merge函数，逐步合并，找出范围

public int[] smallestRange(int[][] nums) { PriorityQueue<Element> pq = new PriorityQueue<Element>(new Comparator<Element>() { public int compare(Element a, Element b) { return a.val - b.val; } }); int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE; for (int i = 0; i < nums.length; i++) { Element e = new Element(i, 0, nums[i][0]); pq.offer(e); max = Math.max(max, nums[i][0]); } int range = Integer.MAX_VALUE; int start = -1, end = -1; while (pq.size() == nums.length) { Element curr = pq.poll(); if (max - curr.val < range) { range = max - curr.val; start = curr.val; end = max; } if (curr.idx + 1 < nums[curr.row].length) { curr.idx = curr.idx + 1; curr.val = nums[curr.row][curr.idx]; pq.offer(curr); if (curr.val > max) { max = curr.val; } } } return new int[] { start, end }; } class Element { int val; int idx; int row; public Element(int r, int i, int v) { val = v; idx = i; row = r; } }